#include "highway.h"
#include <iostream>
using namespace std;
long long int sure[130005],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;
return ask(w);
}
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;
}
for(int i=0;i<m;i++)p[i]=0;
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]=-1;
father[start][1]=-1;
father[end][0]=start;
father[end][1]=point;
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<<i<<" "<<tree[i][0]<<endl;
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++)
{
int g=tree[i][0];
while(p[father[g][1]]==1)
{
p[father[g][1]]=0;
g=father[g][0];
}
//cout<<endl;
}
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<<"建樹"<<g<<endl;
while(p[father[g][1]]==0)
{
//cout<<g<<" "<<father[g][0]<<" ";
p[father[g][1]]=1;
g=father[g][0];
}
//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:192:24: warning: 'endans' may be used uninitialized in this function [-Wmaybe-uninitialized]
while(sure[father[o][1]]==1)
~~~~~~~~~~~^
highway.cpp:127:24: warning: 'startans' may be used uninitialized in this function [-Wmaybe-uninitialized]
while(sure[father[o][1]]==1)
~~~~~~~~~~~^
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 |
352 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
424 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
1544 KB |
Output is correct |
| 2 |
Correct |
34 ms |
2912 KB |
Output is correct |
| 3 |
Correct |
50 ms |
4196 KB |
Output is correct |
| 4 |
Incorrect |
139 ms |
11480 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
508 KB |
Output is correct |
| 2 |
Correct |
21 ms |
1528 KB |
Output is correct |
| 3 |
Correct |
173 ms |
9456 KB |
Output is correct |
| 4 |
Incorrect |
146 ms |
12144 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
1676 KB |
Output is correct |
| 2 |
Correct |
32 ms |
1724 KB |
Output is correct |
| 3 |
Incorrect |
187 ms |
12604 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
1684 KB |
Output is correct |
| 2 |
Correct |
49 ms |
1736 KB |
Output is correct |
| 3 |
Correct |
300 ms |
12212 KB |
Output is correct |
| 4 |
Correct |
291 ms |
13012 KB |
Output is correct |
| 5 |
Correct |
313 ms |
12992 KB |
Output is correct |
| 6 |
Incorrect |
332 ms |
14388 KB |
Output is incorrect: {s, t} is wrong. |
| 7 |
Halted |
0 ms |
0 KB |
- |
