#include "highway.h"
#include <iostream>
using namespace std;
long long int tag[90005],tree[900005][2],t[1000005][2],father[900005][2],cnt,road[900005],map[2600005][2],m,p[1300005];
long long int check()
{
vector<int> w(m);
for(int i=0;i<m;i++)w[i]=p[i];
for(int i=0;i<m;i++)p[i]=0;
int e=ask(w);
//cout<<"解"<<e<<endl;
return e;
}
void find_pair(int n,vector<int> u,vector<int> v,int a, int b) {
m=u.size();
//for(int i=0;i<m;i++)sure[i]=1;
for(int i=0;i<n;i++)road[i]=-1;
for(int i=0;i<m;i++)
{
int x=u[i],y=v[i];
map[i*2][0]=x;
map[i*2][1]=road[y];
road[y]=i*2;
map[i*2+1][0]=y;
map[i*2+1][1]=road[x];
road[x]=i*2+1;
}
for(int i=0;i<m;i++)p[i]=1;
cnt=check();
//cout<<cnt<<endl;
int point;
int l=0,r=m-1;
while(l<=r)
{
int mid=(l+r)/2;
for(int i=0;i<m;i++)p[i]=1;
for(int i=l;i<=mid;i++)p[i]=0;
long long int tmp=check();
if(tmp<cnt)
{
r=mid-1;
point=mid;
}
else l=mid+1;
}
cnt=check();
long long int start=u[point];
long long int end=v[point];
int tp=1,tpp=2;
t[1][0]=start;
t[1][1]=0;
t[2][0]=end;
t[2][1]=1;
tree[0][0]++;
tree[0][1]++;
tree[1][0]=start;
tree[1][1]=end;
tag[start]=1;
tag[end]=1;
for(int i=0;i<n;i++)father[i][0]=-2;
//cout<<start<<" "<<end<<endl;
father[start][0]=end;
father[start][1]=point;
father[end][0]=start;
father[end][1]=point;
p[130000]=1;
while(tp<=tpp)
{
int now=t[tp][0];
int g=road[now];
while(g!=-1)
{
if(tag[map[g][0]]==0)
{
tag[map[g][0]]=1;
father[map[g][0]][0]=now;
father[map[g][0]][1]=g/2;
tpp++;
t[tpp][0]=map[g][0];
t[tpp][1]=t[tp][1];
tree[0][t[tp][1]]++;
tree[tree[0][t[tp][1]]][t[tp][1]]=map[g][0];
}
g=map[g][1];
}
tp++;
}
//cout<<endl;
l=1,r=tree[0][0];
int startans;
//cout<<"first"<<endl;
while(l<=r)
{
int mid=(l+r)/2;
//cout<<l<<" "<<r<<endl;
for(int i=1;i<=tree[0][0];i++)
{
int g=tree[i][0];
//cout<<tree[i][0]<<" ";
while(p[father[g][1]]==0)
{
//cout<<father[g][1]<<" ";
p[father[g][1]]=1;
g=father[g][0];
}
}
for(int i=l;i<=mid;i++)
{
//cout<<tree[i][0]<<endl;
int g=tree[i][0];
//cout<<i<<" "<<tree[i][0]<<" ";
while(p[father[g][1]]==1)
{
//cout<<father[g][0]<<" ";
p[father[g][1]]=0;
g=father[g][0];
}
//cout<<endl;
}
//cout<<endl;
int o=0;
/*while(sure[father[o][1]]==1)
{
cout<<father[o][0]<<" "<<p[father[o][1]]<<endl;
sure[father[o][1]]=0;
p[father[o][1]]=0;
o=father[o][0];
}*/
//for(int i=0;i<m;i++)sure[i]=1;
long long int tmp=check();
//cout<<tmp<<endl;
if(tmp==cnt)
{
startans=tree[mid][0];
r=mid-1;
}
else l=mid+1;
}
int o=startans;
/*while(sure[father[o][1]]==1)
{
cout<<father[o][0]<<endl;
sure[father[o][1]]=0;
//p[father[o][1]]=0;
o=father[o][0];
}*/
//cout<<"firstend"<<endl;
//for(int i=0;i<m;i++)cout<<p[i]<<" ";
//cout<<endl;
//cout<<cnt<<endl;
//cout<<endl;
//for(int i=0;i<m;i++)p[i]=1;
//cout<<cnt<<endl;
//cout<<cnt<<endl;
l=1,r=tree[0][1];
int endans;
while(l<=r)
{
int mid=(l+r)/2;
//cout<<"二分"<<l<<" "<<r<<endl;
for(int i=1;i<=tree[0][1];i++)
{
int g=tree[i][1];
//cout<<tree[i][1]<<" ";
//cout<<"建樹"<<g<<endl;
while(p[father[g][1]]==0)
{
//cout<<g<<" "<<father[g][0]<<" ";
p[father[g][1]]=1;
g=father[g][0];
}
//cout<<endl;
}
//cout<<endl;
for(int i=l;i<=mid;i++)
{
if(tree[i][1]==56305)cout<<i<<endl;
int g=tree[i][1];
//cout<<i<<" "<<tree[i][1]<<endl;
while(p[father[g][1]]==1)
{
//cout<<father[g][1]<<" ";
p[father[g][1]]=0;
g=father[g][0];
}
}
/*o=56305;
while(sure[father[o][1]]==1)
{
//cout<<father[o][0]<<" "<<p[father[o][1]]<<endl;
sure[father[o][1]]=0;
//p[father[o][1]]=0;
o=father[o][0];
}*/
//for(int i=0;i<m;i++)sure[i]=1;
//cout<<endl;
long long int tmp=check();
//cout<<tmp<<endl;
if(tmp==cnt)
{
endans=tree[mid][1];
r=mid-1;
}
else l=mid+1;
}
o=endans;
/*while(sure[father[o][1]]==1)
{
//cout<<father[o][0]<<endl;
sure[father[o][1]]=0;
//p[father[o][1]]=0;
o=father[o][0];
}*/
//cout<<startans<<" "<<endans<<endl;
answer(startans,endans);
}
Compilation message
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:123:7: warning: unused variable 'o' [-Wunused-variable]
int o=0;
^
highway.cpp:141:6: warning: variable 'o' set but not used [-Wunused-but-set-variable]
int o=startans;
^
highway.cpp:217:8: warning: 'endans' may be used uninitialized in this function [-Wmaybe-uninitialized]
answer(startans,endans);
~~~~~~^~~~~~~~~~~~~~~~~
highway.cpp:217:8: warning: 'startans' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:48:29: warning: 'point' may be used uninitialized in this function [-Wmaybe-uninitialized]
long long int start=u[point];
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
432 KB |
Output is correct |
| 3 |
Correct |
2 ms |
344 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
348 KB |
Output is correct |
| 7 |
Correct |
2 ms |
432 KB |
Output is correct |
| 8 |
Correct |
2 ms |
296 KB |
Output is correct |
| 9 |
Correct |
2 ms |
296 KB |
Output is correct |
| 10 |
Correct |
2 ms |
348 KB |
Output is correct |
| 11 |
Correct |
2 ms |
348 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
16 ms |
1528 KB |
Output is correct |
| 3 |
Correct |
233 ms |
11312 KB |
Output is correct |
| 4 |
Incorrect |
188 ms |
11292 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
1464 KB |
Output is correct |
| 2 |
Correct |
35 ms |
2716 KB |
Output is correct |
| 3 |
Correct |
71 ms |
4068 KB |
Output is correct |
| 4 |
Incorrect |
156 ms |
10764 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
416 KB |
Output is correct |
| 2 |
Correct |
26 ms |
1396 KB |
Output is correct |
| 3 |
Correct |
165 ms |
8896 KB |
Output is correct |
| 4 |
Incorrect |
165 ms |
11220 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
1584 KB |
Output is correct |
| 2 |
Correct |
50 ms |
1684 KB |
Output is correct |
| 3 |
Incorrect |
228 ms |
11844 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1584 KB |
Output is correct |
| 2 |
Correct |
24 ms |
1640 KB |
Output is correct |
| 3 |
Correct |
280 ms |
11316 KB |
Output is correct |
| 4 |
Correct |
293 ms |
12184 KB |
Output is correct |
| 5 |
Correct |
307 ms |
12212 KB |
Output is correct |
| 6 |
Incorrect |
339 ms |
13320 KB |
Output is incorrect: {s, t} is wrong. |
| 7 |
Halted |
0 ms |
0 KB |
- |
