#include <vector>
#include "incursion.h"
#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
std::vector<int> mark(std::vector<std::pair<int, int>> f, int safe) {
int n = f.size() + 1;
safe -= 1;
vector<int> sz(n), maxsz(n);
vector<vector<int>> adj(n);
vector<int> par(n, -1), to_safe(n, -2);
for (auto [u, v] : f) {
adj[u - 1].push_back(v - 1);
adj[v - 1].push_back(u - 1);
}
function<void(int, int)> dfs_sz = [&](int node, int par) {
sz[node] = 1;
maxsz[node] = 0;
for (auto v : adj[node]) {
if (v == par) continue;
dfs_sz(v, node);
maxsz[node] = max(maxsz[node], sz[v]);
sz[node] += sz[v];
}
maxsz[node] = max(maxsz[node], n - sz[node]);
};
dfs_sz(0, -1);
// check centroid count
int cent_req = *min_element(maxsz.begin(), maxsz.end());
vector<int> centroids;
for (int i = 0; i < n; ++i) {
if (maxsz[i] == cent_req) {
centroids.push_back(i);
}
}
assert(0 < centroids.size() && centroids.size() <= 2);
function<void(int, vector<int>&)> dfs_par = [&](int node, vector<int>& par) {
for (auto v : adj[node]) {
if (v == par[node]) continue;
par[v] = node;
dfs_par(v, par);
}
};
dfs_par(centroids[0], par);
dfs_par(safe, to_safe);
if (centroids.size() == 2) {
par[centroids[0]] = centroids[1];
}
vector<int> ret;
// true -> go to parent
// false -> go to other child
for (int i = 0; i < n; ++i) {
if (to_safe[i] == par[i]) {
ret.push_back(true);
} else {
ret.push_back(false);
}
}
return ret;
}
void locate(std::vector<std::pair<int, int>> F, int node, int t) {
node -= 1;
int n = F.size() + 1;
vector<vector<int>> adj(n);
vector<int> sz(n), maxsz(n);
vector<int> par(n, -1);
vector<bool> visited(n, false);
visited[node] = true;
for (auto [u, v] : F) {
adj[u - 1].push_back(v - 1);
adj[v - 1].push_back(u - 1);
}
function<void(int, int)> dfs_sz = [&](int node, int par) {
sz[node] = 1;
maxsz[node] = 0;
for (auto v : adj[node]) {
if (v == par) continue;
dfs_sz(v, node);
maxsz[node] = max(maxsz[node], sz[v]);
sz[node] += sz[v];
}
maxsz[node] = max(maxsz[node], n - sz[node]);
};
dfs_sz(0, -1);
// check centroid count
int cent_req = *min_element(maxsz.begin(), maxsz.end());
vector<int> centroids;
for (int i = 0; i < n; ++i) {
if (maxsz[i] == cent_req) {
centroids.push_back(i);
}
}
assert(0 < centroids.size() && centroids.size() <= 2);
function<void(int, vector<int>&)> dfs_par = [&](int node, vector<int>& par) {
sort(adj[node].begin(), adj[node].end(), [&](int u, int v) { return sz[u] > sz[v]; });
for (auto v : adj[node]) {
if (v == par[node]) continue;
par[v] = node;
dfs_par(v, par);
}
};
dfs_par(centroids[0], par);
if (centroids.size() == 2) {
par[centroids[0]] = centroids[1];
}
auto go = [&](int node) {
visited[node] = true;
return visit(node + 1);
};
while (true) {
if (t) {
if (visited[par[node]]) {
go(par[node]);
break;
}
t = go(par[node]);
node = par[node];
continue;
}
// try all ways
bool moved = false;
for (auto v : adj[node]) {
if (v == par[node]) continue;
if (visited[v]) continue;
int ct = go(v);
if (ct) {
go(node);
} else {
t = ct;
node = v;
moved = true;
break;
}
}
if (!moved) break;
}
}
#ifndef EVAL
#include "sample_grader.cpp"
#endif
Compilation message
trade.cpp:2:10: fatal error: incursion.h: No such file or directory
2 | #include "incursion.h"
| ^~~~~~~~~~~~~
compilation terminated.
