#include "highway.h"
#include <iostream>
using namespace std;
unsigned 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;
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<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=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;
father[start][0]=-1;
father[start][1]=130000;
father[end][0]=-1;
father[end][1]=130000;
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++;
}
for(int i=1;i<=tree[0][0];i++)
{
int g=tree[i][0];
//cout<<tree[i][0]<<" ";
while(p[father[g][1]]==1)
{
p[father[g][1]]=0;
g=father[g][0];
}
}
//cout<<endl;
cnt=check();
l=1,r=tree[0][0];
int startans;
while(l<=r)
{
int mid=(l+r)/2;
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();
if(tmp==cnt)
{
startans=tree[mid][0];
r=mid-1;
}
else l=mid+1;
}
for(int i=1;i<=tree[0][1];i++)
{
int g=tree[i][1];
//cout<<tree[i][1]<<" ";
while(p[father[g][1]]==1)
{
p[father[g][1]]=0;
g=father[g][0];
}
}
//cout<<endl;
for(int i=0;i<m;i++)p[i]=1;
cnt=check();
//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=l;i<=mid;i++)
{
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];
}
}
//cout<<endl;
long long int tmp=check();
//cout<<tmp<<endl;
if(tmp==cnt)
{
endans=tree[mid][1];
r=mid-1;
}
else l=mid+1;
}
//cout<<startans<<" "<<endans<<endl;
answer(startans,endans);
}
Compilation message
highway.cpp: In function 'long long int check()':
highway.cpp:9:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<m;i++)w[i]=p[i];
~^~
highway.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<m;i++)p[i]=1;
~^~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<m;i++)
~^~
highway.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<m;i++)p[i]=1;
~^~
highway.cpp:36:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(tmp<cnt)
~~~^~~~
highway.cpp:82:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<=tree[0][0];i++)
~^~~~~~~~~~~~
highway.cpp:110:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(tmp==cnt)
~~~^~~~~
highway.cpp:117:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<=tree[0][1];i++)
~^~~~~~~~~~~~
highway.cpp:128:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<m;i++)p[i]=1;
~^~
highway.cpp:151:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(tmp==cnt)
~~~^~~~~
highway.cpp:159:8: warning: 'endans' may be used uninitialized in this function [-Wmaybe-uninitialized]
answer(startans,endans);
~~~~~~^~~~~~~~~~~~~~~~~
highway.cpp:159:8: warning: 'startans' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:43: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 |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output is incorrect: {s, t} is wrong. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
492 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
1528 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
404 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
1396 KB |
Output is incorrect: {s, t} is wrong. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
1552 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
1552 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
