#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
vector<ii> E;
struct tree {
int n;
vi par, par_cent, sz;
vector<vi> L, G;
tree(int N) : n(N), L(N), par(N), par_cent(N), sz(N), G(N) {}
void add_edge(int u, int v) {
L[u].push_back(v);
L[v].push_back(u);
}
void init() {
vi on(n, 1);
function<void(int, int)> dfs_sz = [&](int u, int p) {
sz[u] = 1;
for(auto it : L[u]) {
if(on[it] && it != p) {
dfs_sz(it, u);
sz[u] += sz[it];
}
}
};
function<int(int, int, int)> find_c = [&](int u, int p, int slim) {
for(auto it : L[u])
if(on[it] && it != p && 2 * sz[it] > slim) return find_c(it, u, slim);
return u;
};
function<void(int, int) > dfs_cent = [&](int u, int pc) {
dfs_sz(u, -1);
int c = find_c(u, -1, sz[u]);
on[c] = 0;
par_cent[c] = pc;
if(pc != -1) {
G[pc].push_back(c);
}
for(auto it : L[c])
if(on[it]) dfs_cent(it, c);
};
dfs_cent(0, -1);
}
void solve() {
function<void(int, int, vi&)> dfs_comp = [&](int u, int p, vi& V) {
V.push_back(u);
for(auto it : G[u])
dfs_comp(it, u, V);
};
int cost_baza = ask(vi(E.size(), 0));
auto dif = [&](int u, vector<vi>& Fii, int st, int dr) {
set<int> S = {u};
for(int i = st; i <= dr; ++i)
for(auto it : Fii[i]) S.insert(it);
vi w;
for(auto [u, v] : E) {
if(S.count(u) + S.count(v))
w.push_back(1);
else
w.push_back(0);
}
return ask(w) - cost_baza;
};
vi capete;
function<void(int, int, int)> dfs_solve = [&](int c, int pc, int nr) {
vector<vi> comp_fii;
for(auto it : G[c]) {
comp_fii.push_back(vi());
dfs_comp(it, c, comp_fii.back());
}
int pst = -1, pdr = comp_fii.size(), nrfii = comp_fii.size();
int v = dif(c, comp_fii, 0, nrfii - 1);
if(!v) {
if(nr == 1) { // v e unul dintre s & t
capete.push_back(v);
return;
} else {
///uhhh, wtf?
assert(0);
}
}
for(int step = 31 - __builtin_clz(nrfii); step >= 0; --step) {
if(pst + (1 << step) < nrfii) {
if(!dif(c, comp_fii, 0, pst + (1 << step)))
pst += (1 << step);
}
if(pdr - (1 << step) >= 0) {
if(!dif(c, comp_fii, pdr - (1 << step), nrfii - 1))
pdr -= (1 << step);
}
}
++pst;
--pdr;
};
assert(capete.size() == 2);
}
int cine(int rad) {
vi niv(n);
function<void(int, int, int)> dfs = [&](int u, int p, int li) {
niv[u] = li;
for(auto it : L[u]) {
if(it != p) {
dfs(it, u, li + 1);
}
}
};
vi re;
for(int i = 0; i < n; ++i) {
re.push_back(i);
}
dfs(rad, -1, 0);
sort(re.begin(), re.end(), [&](int a, int b) { return niv[a] < niv[b]; });
int st = 0, dr = n - 1, mij;
int q0 = 0;
auto query = [&](int p) {
set<int> I;
for(int i = 0; i <= p; ++i)
I.insert(re[i]);
vi w;
for(auto [u, v] : E) {
if(I.count(u) && I.count(v)) w.push_back(1);
else w.push_back(0);
}
int v = ask(w) - q0;
// cout << "query( " << p << ") este " << v << "\n";
return v + q0;
};
q0 = query(dr);
// cout << "ord: ";
// for(auto it : re)
// cout << it << " ";
// cout << "\n";
int cm = query(dr);
while(st < dr) {
mij = (st + dr) / 2;
if(query(mij) == q0) {
dr = mij;
} else
st = mij + 1;
}
return re[st];
}
};
void find_pair(int N, vi U, vi V, int A, int B) {
tree T(N);
for(int i = 0; i < U.size(); ++i) {
T.add_edge(U[i], V[i]);
E.push_back({U[i], V[i]});
}
T.init();
int s = T.cine(0);
int t = T.cine(s);
cout << s << " " << t << "\n";
answer(s, t);
}
Compilation message
highway.cpp: In constructor 'tree::tree(int)':
highway.cpp:13:16: warning: 'tree::L' will be initialized after [-Wreorder]
13 | vector<vi> L, G;
| ^
highway.cpp:12:8: warning: 'vi tree::par' [-Wreorder]
12 | vi par, par_cent, sz;
| ^~~
highway.cpp:15:5: warning: when initialized here [-Wreorder]
15 | tree(int N) : n(N), L(N), par(N), par_cent(N), sz(N), G(N) {}
| ^~~~
highway.cpp: In member function 'int tree::cine(int)':
highway.cpp:147:13: warning: unused variable 'cm' [-Wunused-variable]
147 | int cm = query(dr);
| ^~
highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:161:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | for(int i = 0; i < U.size(); ++i) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
624 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
3544 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
628 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
214 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
193 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
