#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;std::vector<int>u,v;std::vector<std::pair<int,int>>g[90001];
int sub12(int src,int ban)
{
vector<int>d(n,1e9),e(n,-1);
queue<pair<int,int>>q; q.emplace(d[src]=0,src);
while(q.size()){auto[c,u]=q.front();q.pop();for(auto[v,i]:g[u])if(ban-i&&d[v]>c+1)q.emplace(d[v]=c+1,v),e[v]=i;}
long long need; {vector<int>qq(m,1);for(int i=0;i<n;++i)if(~e[i])qq[e[i]]=0;qq[ban]=0;need=ask(qq);}
vector<int>c;
for(int i=0;i<n;++i)if(d[i]<1e9)c.push_back(i);
sort(c.begin(),c.end(),[&d](int i,int v){return d[i]<d[v];});
int z=0,l=0,r=c.size()-1;
while(l<=r){
int y=(l+r)/2;
vector<int>qq(m,1);
qq[ban]=0;
for(int i=1;i<=y;++i)if(~e[c[i]])qq[e[c[i]]]=0;
if (ask(qq)==need)z=c[y],r=y-1;
else l=y+1;
}
return z;
}
void sub1234(){
long long need; {vector<int>qq(m,1); need=ask(qq);}
auto dt = need / b;
long long light = dt * a;
int e1,l=0,r=m-1;
while(l<=r) {
int y=(l+r)/2;
vector<int>qq(m);
for(int i=0;i<=y;++i)qq[i]=1;
if(ask(qq)>light)r=y-1,e1=y;
else l=y+1;
}
int p=u[e1],q=v[e1],s=sub12(p,e1),t=sub12(q,e1);
answer(s,t);
}
auto shortpath(int src){
vector<int>d(n,1e9);
queue<pair<int,int>>q;q.emplace(d[src]=0,src);
while(q.size()){auto[c,u]=q.front();q.pop();for(auto [v,_]:g[u])if(d[v]>c+1)q.emplace(d[v]=c+1,v);}
return d;
}
int tree(int rt,std::set<int>&S,std::set<int>&T,int e1){
vector<int>d(n,1e9),e(n,-1);
queue<pair<int,int>>q; q.emplace(d[rt]=0,rt);
while(q.size()){auto[c,u]=q.front();q.pop();for(auto[v,i]:g[u])if(S.count(v)&&d[v]>c+1)q.emplace(d[v]=c+1,v),e[v]=i;}
long long need;
std::set<int>WhatisThis;
{
vector<int>qq(m,1);
//for(int i=0;i<m;++i) if((S.count(u[i])&&S.count(v[i]))|| (T.count(u[i])||T.count(v[i]))); else qq[i]=1;
for(int i=0;i<m;++i)
{
if((S.count(u[i])&&S.count(v[i])))qq[i]=0;
if((T.count(u[i])&&T.count(v[i])))qq[i]=0;
}
qq[e1]=0;
need=ask(qq);
}
vector<int>c;
for(int i=0;i<n;++i)if(~e[i])c.push_back(i);
sort(c.begin(),c.end(),[&d](int i,int v){return d[i]<d[v];});
//printf(" C is : ");for(int x : c)printf("%d ",x);puts("");
int z=rt,l=0,r=c.size()-1;
while(l<=r){
int y=(l+r)/2;
vector<int>qq(m,0);
for(int i=0;i<m;++i){
if(S.count(u[i])&&S.count(v[i]))qq[i]=1;
else if (T.count(v[i])&&T.count(u[i]))qq[i]=0;
else qq[i]=1;
}
for(int i=0;i<=y;++i)if(~e[c[i]])qq[e[c[i]]]=0;
qq[e1]=0;
if (ask(qq)==need)z=c[y],r=y-1;
else l=y+1;
}
return z;
}
void sub6()
{
long long light; {vector<int>qq(m,0); light=ask(qq);}
int e1,l=0,r=m-1;
while(l<=r) {
int y=(l+r)/2;
vector<int>qq(m);
for(int i=0;i<=y;++i)qq[i]=1;
if(ask(qq)>light)r=y-1,e1=y;
else l=y+1;
}
int U=u[e1],V=v[e1];
auto du=shortpath(U),dv=shortpath(V);
set<int>S,T;
for(int i=0;i<n;++i)if(du[i]<dv[i])S.insert(i);else T.insert(i);
int s = tree(U,S,T,e1);
int t = tree(V,T,S,e1);
//printf(" ST %d %d\n",s,t);
answer(s,t);
}
void sub5(){
int l=0,r=n-1;
auto diffset = [&](vector<int>&grp){
vector<int>qq(m);
for(int i=0;i<m;++i)if(grp[u[i]]^grp[v[i]])qq[i]=0;else qq[i]=1;
if(ask(qq)&1)return 1;return 0;
};
vector<int> gs,gt,grp(n);
for(int b=0;b<=17;++b){
for(int i=0;i<n;++i)
grp[i]=(i>>b)&1;
if(diffset(grp)) {break;}
}
for(int i=0;i<n;++i)if(grp[i])gt.push_back(i);else gs.push_back(i);
while(gs.size()>1){
vector<int>n1,n2,test(n);
for(int i=0;i<gs.size()/2;++i)n1.push_back(gs[i]);
for(int i=gs.size()/2;i<gs.size();++i)n2.push_back(gs[i]);
for(int x:n1)test[x]=1;
if(diffset(test))gs=n1;
else gs=n2;
}
while(gt.size()>1){
vector<int>n1,n2;
for(int i=0;i<gt.size()/2;++i)n1.push_back(gt[i]);
for(int i=gt.size()/2;i<gt.size();++i)n2.push_back(gt[i]);
vector<int> test(n);for(int x:n1)test[x]=1;
if(diffset(test))gt=n1;
else gt=n2;
}
answer(gs[0],gt[0]);
}
void find_pair(int n_, std::vector<int> u_, std::vector<int> v_, int A_, int B_) {
n=n_,u=u_,v=v_,a=A_,b=B_;m=u.size();
for(int i=0;i<m;++i)g[u[i]].push_back({v[i],i}),g[v[i]].push_back({u[i],i});
return sub6();
if(a==1&&b==2)return sub5();
sub1234();
}
Compilation message
highway.cpp: In lambda function:
highway.cpp:133:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
133 | if(ask(qq)&1)return 1;return 0;
| ^~
highway.cpp:133:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
133 | if(ask(qq)&1)return 1;return 0;
| ^~~~~~
highway.cpp: In function 'void sub5()':
highway.cpp:148:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
148 | for(int i=0;i<gs.size()/2;++i)n1.push_back(gs[i]);
| ~^~~~~~~~~~~~
highway.cpp:149:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int i=gs.size()/2;i<gs.size();++i)n2.push_back(gs[i]);
| ~^~~~~~~~~~
highway.cpp:157:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
157 | for(int i=0;i<gt.size()/2;++i)n1.push_back(gt[i]);
| ~^~~~~~~~~~~~
highway.cpp:158:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for(int i=gt.size()/2;i<gt.size();++i)n2.push_back(gt[i]);
| ~^~~~~~~~~~
highway.cpp:128:9: warning: unused variable 'l' [-Wunused-variable]
128 | int l=0,r=n-1;
| ^
highway.cpp:128:13: warning: unused variable 'r' [-Wunused-variable]
128 | int l=0,r=n-1;
| ^
highway.cpp: In function 'void sub6()':
highway.cpp:114:15: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
114 | int U=u[e1],V=v[e1];
| ^
highway.cpp: In function 'void sub1234()':
highway.cpp:46:15: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
46 | int p=u[e1],q=v[e1],s=sub12(p,e1),t=sub12(q,e1);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2560 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2620 KB |
Output is correct |
| 2 |
Correct |
49 ms |
3892 KB |
Output is correct |
| 3 |
Correct |
867 ms |
14592 KB |
Output is correct |
| 4 |
Correct |
1143 ms |
15056 KB |
Output is correct |
| 5 |
Correct |
1103 ms |
14588 KB |
Output is correct |
| 6 |
Correct |
916 ms |
14596 KB |
Output is correct |
| 7 |
Correct |
1190 ms |
14840 KB |
Output is correct |
| 8 |
Correct |
1092 ms |
14840 KB |
Output is correct |
| 9 |
Correct |
885 ms |
14588 KB |
Output is correct |
| 10 |
Correct |
986 ms |
14824 KB |
Output is correct |
| 11 |
Correct |
1330 ms |
14424 KB |
Output is correct |
| 12 |
Correct |
1362 ms |
14144 KB |
Output is correct |
| 13 |
Correct |
1329 ms |
14460 KB |
Output is correct |
| 14 |
Correct |
1350 ms |
14188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
3800 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2612 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
3932 KB |
Output is correct |
| 2 |
Correct |
78 ms |
3964 KB |
Output is correct |
| 3 |
Correct |
1285 ms |
14980 KB |
Output is correct |
| 4 |
Execution timed out |
1643 ms |
16008 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
3892 KB |
Output is correct |
| 2 |
Correct |
82 ms |
3960 KB |
Output is correct |
| 3 |
Execution timed out |
1551 ms |
15300 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
