#include "highway.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ld long double
#define F first
#define S second
#define mp make_pair
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=2e5+500;
const ll inf=1e9+900;
const ll mod=1e9+7;
vector<ll> ger[maxn];
bool hazf[maxn];
ll s[maxn];
ll t[maxn];
ll sz[maxn];
ll st[maxn];
ll et[maxn];
ll tt=0;
ll m,a,b,adi,n;
vector<int> w;
void dfsas(ll a,ll tim,ll p=-1){
for(auto e:ger[a]){
ll v=(s[e]^t[e]^a);
if(v!=p && !hazf[v]){
if(et[v]<=tim){
w[e]=1;
continue;
}
dfsas(v,tim,a);
}
}
}
ll as(vector<ll> vec,ll rot){
w.clear();
w.resize(m);
fill(w.begin(),w.end(),0);
dfsas(rot,et[vec.back()]);
return ask(w);
}
ll finds(vector<ll> vec,ll rot){
if(vec.size()==1)return vec[0];
vector<ll> l,r;
for(ll i=0;i<(ll)vec.size()/2;i++){
l.pb(vec[i]);
}
for(ll i=(ll)vec.size()/2;i<vec.size();i++){
r.pb(vec[i]);
}
if(as(l,rot)==adi+b-a){
return finds(l,rot);
}
return finds(r,rot);
}
pii findst(vector<ll> vec,ll rot){
if(vec.size()==2)return mp(vec[0],vec[1]);
vector<ll> l,r;
for(ll i=0;i<(ll)vec.size()/2;i++){
l.pb(vec[i]);
}
for(ll i=(ll)vec.size()/2;i<vec.size();i++){
r.pb(vec[i]);
}
ll p=as(l,rot);
if(p==adi+b-a+b-a){
return findst(l,rot);
}
if(p==adi){
return findst(r,rot);
}
ll fa=finds(l,rot);
adi+=b-a;
ll fb=finds(r,rot);
return mp(fa,fb);
}
vector<ll> topol;
void dfsst(ll a,ll p=-1){
st[a]=tt;
for(auto e:ger[a]){
ll v=(s[e]^t[e]^a);
if(v!=p && !hazf[v]){
dfsst(v,a);
}
}
topol.pb(a);
et[a]=tt;
tt++;
}
pii findAnsRot(ll rot){
tt=0;
dfsst(rot);
return findst(topol,rot);
}
void dfssz(ll a,ll p=-1){
sz[a]=1;
for(auto e:ger[a]){
ll v=(s[e]^t[e]^a);
if(v!=p && !hazf[v]){
dfssz(v,a);
sz[a]+=sz[v];
}
}
}
void dfs1(ll a,ll p=-1){
for(auto e:ger[a]){
ll v=(s[e]^t[e]^a);
if(v!=p && !hazf[v]){
w[e]=1;
dfs1(v,a);
}
}
}
ll findCn(ll a,ll x,ll p=-1){
for(auto e:ger[a]){
ll v=(s[e]^t[e]^a);
if(v!=p && !hazf[v] && sz[v]>x){
return findCn(v,x,a);
}
}
return a;
}
ll last;
pii dfs(ll a){
dfssz(a);
if(sz[a]>(last-1)/2)exit(1);;
last=sz[a];
ll cn=findCn(a,sz[a]/2);
dfssz(cn);
w.resize(m);
fill(w.begin(),w.end(),0);
for(auto e:ger[cn]){
ll v=(s[e]^t[e]^cn);
if(!hazf[v]){
w[e]=1;
}
}
ll r=ask(w);
if(r!=adi){
return findAnsRot(cn);
}
hazf[cn]=1;
if(ger[cn].size()>2)exit(1);
fill(w.begin(),w.end(),0);
dfs1(ger[cn][0]);
if(ask(w)==adi){
return dfs(ger[cn][1]);
}
return dfs(ger[cn][0]);
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
a=A;
b=B;
m=V.size();
n=N;
if(m!=n-1){
exit(1);
}
for(ll i=0;i<m;i++){
s[i]=V[i];
t[i]=U[i];
}
for(ll i=0;i<m;i++){
ger[s[i]].pb(i);
ger[t[i]].pb(i);
}
vector<int> w(m);
fill(w.begin(),w.end(),0);
adi=ask(w);
last=2*n+1;
pii e=dfs(0);
answer(e.F,e.S);
}
Compilation message
highway.cpp: In function 'long long int finds(std::vector<long long int>, long long int)':
highway.cpp:56:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i=(ll)vec.size()/2;i<vec.size();i++){
~^~~~~~~~~~~
highway.cpp: In function 'std::pair<long long int, long long int> findst(std::vector<long long int>, long long int)':
highway.cpp:70:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i=(ll)vec.size()/2;i<vec.size();i++){
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4988 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5132 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5044 KB |
Output is correct |
| 4 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 5 |
Runtime error |
6 ms |
5072 KB |
Execution failed because the return code was nonzero |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5204 KB |
Output is correct |
| 2 |
Runtime error |
18 ms |
5772 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
6264 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5112 KB |
Output is correct |
| 2 |
Correct |
40 ms |
6492 KB |
Output is correct |
| 3 |
Runtime error |
153 ms |
10972 KB |
Execution failed because the return code was nonzero |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
5112 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
43 ms |
5116 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
