#include <vector>
#include "incursion.h"
#include <cstdio>
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
#define sz(x) ((int)(x).size())
using pii = pair<int, int>;
using tii = tuple<int, int, int>;
const int nmax = 45e3 + 5;
vector<int> g[nmax];
int area[nmax];
int father[nmax];
#define N uhasfuhafs
int N;
void initarea(int node, int f) {
area[node] = 1;
father[node] = f;
for(auto x : g[node]) {
if(x == f) continue;
initarea(x, node);
area[node] += area[x];
}
return;
}
pii findcentr(int node, int f) {
for(auto x : g[node]) {
if(x == f) continue;
if(area[x] * 2 == N) { return pii{node, x}; }
if(area[x] * 2 > N) { return findcentr(x, node); }
}
return pii{node, node};
}
int make_graph(vector<pii> F) {
for(auto &[a, b] : F) --a, --b;
N = sz(F) + 1;
for(int i = 0; i <= N + 1; i++) g[i].clear();
for(auto [a, b] : F) {
g[a].emplace_back(b);
g[b].emplace_back(a);
}
int cnt = 0;
for(int i = 0; i < N; i++) {
if(sz(g[i]) == 2) cnt++;
}
if(cnt == 1) {
for(int i = 0; i < N; i++)
if(sz(g[i]) == 2) return i;
}
initarea(0, 0);
auto [u_, v_] = findcentr(0, 0);
int root;
if(u_ != v_) {
for(int i = 0; i < sz(g[u_]); i++) {
if(g[u_][i] == v_) {
swap(g[u_][i], g[u_].back());
g[u_].pop_back();
break;
}
}
for(int i = 0; i < sz(g[v_]); i++) {
if(g[v_][i] == u_) {
swap(g[v_][i], g[v_].back());
g[v_].pop_back();
break;
}
}
g[u_].emplace_back(N);
g[v_].emplace_back(N);
g[N].emplace_back(u_);
g[N].emplace_back(v_);
N++;
root = N - 1;
}
else { root = u_; }
initarea(root, root);
for(auto x : g[root])
assert(area[x] * 2 < N);
return root;
}
vector<int> known;
bool dfs(int node, int f, int where) {
bool znayu = node == where;
for(auto x : g[node]) {
if(x == f) continue;
znayu |= dfs(x, node, where);
}
known[node] = znayu;
return known[node];
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
--safe;
int root = make_graph(F);
known.resize(N);
dfs(root, root, safe);
//cerr << root + 1 << '\n';
known.resize(sz(F) + 1);
return known;
}
int go(int x) {
return visit(x +1);
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
--curr;
int root = make_graph(F);
cerr << root << '\n';
for(int i = 0; i< N; i++) {
cerr << i << ": ";
for(auto x : g[i]) cerr << x << ' ';
cerr << '\n';
}
known.assign(N, -1);
if(N != sz(F) + 1)
known.back() = 1;
initarea(root, root);
while(1) {
if(t == 0) {
int u = father[curr];
if(u == sz(F) + 1) {
curr = g[u][0] ^ g[u][1] ^ curr;
t = go(curr);
}
else {
curr = father[curr];
t = go(curr);
}
}
else {
int a = -1, b = -1, c = -1;
for(auto x : g[curr]) {
if(x == father[curr]) continue;
if(a == -1) a = x;
else if(b == -1) b = x;
else c = x;
}
//cerr << curr << ": " << a << ' ' << b << '\n';
COAIE:
if(a == -1 && b == -1 && c == -1) return;
if(b == -1) {
int h = go(a);
if(h == 1) {
curr = a;
t = 1;
continue;
}
go(curr);
return;
}
else if (c == -1) {
if(area[a] < area[b]) swap(a, b);
int h = go(a);
if(h == 1) {
curr = a;
t = 1;
continue;
}
go(curr);
h = go(b);
if(h == 1) {
curr = b;
t = 1;
continue;
}
go(curr);
return;
}
else {
if(area[c] < area[b]) swap(c, b);
if(area[c] < area[a]) swap(c, b);
int h = go(c);
if(h == 1) {
curr = c;
t = 1;
continue;
}
go(curr);
c = -1;
goto COAIE;
}
}
}
}
#undef N
Compilation message
trade.cpp:2:10: fatal error: incursion.h: No such file or directory
2 | #include "incursion.h"
| ^~~~~~~~~~~~~
compilation terminated.
