#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[node] * 2 == N) { return pii{node, x}; }
if(area[node] * 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; i++) g[i].clear();
for(auto [a, b] : F) {
g[a].emplace_back(b);
g[b].emplace_back(a);
}
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_; }
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);
//for(int i = 0; i< N; i++) {
//cerr << i << ": ";
//for(auto x : g[i]) cerr << x << ' ';
//cerr << '\n';
//}
dfs(root, root, safe);
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);
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;
for(auto x : g[curr]) {
if(x == father[curr]) continue;
if(a == -1) a = x;
else b = x;
}
if(a == -1 && b == -1) return;
if(b == -1) {
int h = go(a);
if(h == 1) {
curr = a;
t = 1;
continue;
}
visit(curr);
return;
}
else {
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;
}
}
}
}
#undef N
Compilation message
interface.cpp: In function 'int main()':
interface.cpp:44:55: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
44 | if(fread(T.data(), sizeof(int), 2 * N - 2, stdin) != 2 * N - 2) exit(0);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
interface.cpp:50:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
50 | int l = (numbers.size() == N ? N : 0);
| ~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2820 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
12860 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
8640 KB |
Correct |
| 2 |
Incorrect |
83 ms |
8472 KB |
Not correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2820 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
