POI Spies Optimization

Debugging Help
#1

Problem Info

I’m doing Spies from the POI.

My Work

#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;

/** https://szkopul.edu.pl/problemset/problem/r6tMTfvQFPAEfQioYMCQndQe/site/?key=statement */
int main() {
    int spy_num;
    std::cin >> spy_num;
    vector<int> shadow(spy_num);
    vector<vector<int>> shadowed_by(spy_num);
    for (int p = 0; p < spy_num; p++) {
        std::cin >> shadow[p];
        shadow[p]--;
        shadowed_by[shadow[p]].push_back(p);
    }

    /*
     * -2 = We haven't even got to processing this spy yet.
     * -1 = This spy is part of a tree.
     * >= 0 = This ID of the cycle this spy is in.
     */
    int cycle_id = 0;
    vector<int> part(spy_num, -2);
    for (int p = 0; p < spy_num; p++) {
        if (part[p] != -2) {
            continue;
        }
        vector<int> path{p};
        int at = p;
        while (part[shadow[at]] == -2) {
            at = shadow[at];
            part[at] = -3;  // leave breadcrumbs for this iteration
            path.push_back(at);
        }
        
        bool in_cycle = false;
        for (int i : path) {
            in_cycle = in_cycle || i == shadow[at];
            part[i] = in_cycle ? cycle_id : -1;
        }
        cycle_id++;
    }

    vector<bool> used(spy_num);
    vector<std::pair<int, bool>> assigned(spy_num, {0, true});
    std::function<void(int, int, int)> assign_spies;
    assign_spies = [&] (int at, int prev, int root) {
        for (int n : shadowed_by[at]) {
            if (n == prev || part[n] == part[root]) {
                continue;
            }
            assign_spies(n, at, root);
            if (!used[n] && !used[at]) {
                used[n] = used[at] = true;
                assigned[root].first++;
                if (at == root) {
                    assigned[root].second = false;
                }
            }
        }
    };
    for (int s = 0; s < spy_num; s++) {
        if (part[s] >= 0) {
            assign_spies(s, s, s);
        }
    }
    
    int max_spies = 0;
    vector<bool> cycle_done(cycle_id + 1);
    for (int s = 0; s < spy_num; s++) {
        if (part[s] >= 0 && !cycle_done[part[s]]) {
            cycle_done[part[s]] = true;
            int at = shadow[s];
            int prev = s;
            do {
                max_spies += assigned[at].first;
                if (assigned[prev].second && assigned[at].second) {
                    max_spies++;
                    assigned[at].second = assigned[prev].second = false;
                }
                prev = at;
                at = shadow[at];
            } while (at != shadow[s]);
        }
    }

    cout << max_spies << endl;
}

It follows a greedy strategy like that of Tree Matching in the Tree DP module, trying to match each spy with any unoccupied spy that shadows them.

Although this seems to output the correct answer, it both TLEs and MLEs.
I’m confused about why both of these judgements occur, as the time complexity is linear and I’ve added up all the sizes of the arrays with N=10^6 and only get 19 MB.

#2

Not sure if you took into account that

  • Vectors double in capacity whenever they run out of capacity (which may multiply the memory usage by 2).
  • Empty vectors each take up 24 bytes.

If you want to precisely measure how much memory is currently being used due to vector allocations, you can check the example at the end of this link: C++ named requirements: Allocator - cppreference.com

#3

I don’t think a vector of size 10^6 is “too small”, but thanks. I’ll look into it.

#4

Alright turns out the vector<vector<int>> shadowed_by is the main memory guzzler, taking up over 20 MB of memory. Any hints for how to address this?

#5

Don’t use (nested) vectors.

#6

Don’t use them for what?

#7

Don’t use them in your solution.

#8

Well yeah, obviously.
Which part? There’s two vectors in vector<vector<int>> shadowed_by, so should I somehow manage to make this one-dimensional?