#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]=1;
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]=0;
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;
}
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;
//cout<<cnt<<endl;
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]<<" ";
while(p[father[g][1]]==1)
{
//cout<<father[g][0]<<" ";
p[father[g][1]]=0;
g=father[g][0];
}
}
//cout<<endl;
for(int i=l;i<=mid;i++)
{
//cout<<tree[i][0]<<" ";
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;
//cout<<p[father[30635][1]]<<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];
//cout<<startans<<endl;
r=mid-1;
}
else l=mid+1;
}
//cout<<startans<<endl;
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][0];i++)
{
int g=tree[i][0];
//cout<<tree[i][1]<<" ";
//cout<<"建樹"<<g<<endl;
while(p[father[g][1]]==1)
{
//cout<<g<<" "<<father[g][0]<<" ";
p[father[g][1]]=0;
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];
//cout<<endans<<endl;
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:146:6: warning: variable 'o' set but not used [-Wunused-but-set-variable]
int o=startans;
^
highway.cpp:223:8: warning: 'endans' may be used uninitialized in this function [-Wmaybe-uninitialized]
answer(startans,endans);
~~~~~~^~~~~~~~~~~~~~~~~
highway.cpp:223:8: warning: 'startans' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:47: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 |
Incorrect |
2 ms |
376 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
1400 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
488 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
1596 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
1604 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
