## 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.