Submission #1073110

#TimeUsernameProblemLanguageResultExecution timeMemory
1073110vjudge1Tricks of the Trade (CEOI23_trade)C++17
Compilation error
0 ms0 KiB
#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 (stderr)

trade.cpp:2:10: fatal error: incursion.h: No such file or directory
    2 | #include "incursion.h"
      |          ^~~~~~~~~~~~~
compilation terminated.