#include "highway.h"
#include <iostream>
using namespace std;
unsigned long long int ta[130005],m,p[1300005],amoney,bmoney,t,cnt,n,tag[1300005],road[1300005],map[2600005][2],sumlength,length,point,startans=-1,endans=-1,tree[1300005],trueroad,start=-1,a[1000005],father[1000005][2];
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);
}
int find(int s,int e)
{
if(s==e)
{
start=s;
return 0;
}
int mid=(s+e)/2;
for(int i=s;i<=mid;i++)p[i]=1;
t=check();
if(t>cnt)find(s,mid);
else find(mid+1,e);
}
int buildtree(int xx)
{
int pt=1,ppt=1;
ta[pt]=xx;
while(pt<=ppt)
{
int x=ta[pt];
int p=road[x];
int c=0;
while(p!=-1)
{
if(tag[map[p][0]]==0)
{
c=1;
ppt++;
tag[map[p][0]]=1;
father[map[p][0]][0]=x;
father[map[p][0]][1]=p/2;
//buildtree(map[p][0]);
ta[ppt]=map[p][0];
}
p=map[p][1];
}
if(c==0)
{
a[0]++;
a[a[0]]=x;
}
pt++;
}
}
int findroad(int x)
{
if(x==point || p[father[x][1]]==1)return 0;
p[father[x][1]]=1;
findroad(father[x][0]);
}
int findtwo(int s,int e)
{
//cout<<"二分"<<s<<" "<<e<<endl;
//for(int i=s;i<=e;i++)cout<<a[i]<<" ";
//cout<<endl;
if(s==e)
{
trueroad=a[s];
findroad(a[s]);
t=check();
//cout<<"總花費"<<t<<" "<<cnt<<endl;
length=(t-cnt)/(bmoney-amoney);
return 0;
}
for(int i=s;i<=(s+e)/2;i++)
{
findroad(a[i]);
}
int l=check();
if(l==cnt)findtwo((s+e)/2+1,e);
for(int i=(s+e)/2+1;i<=e;i++)findroad(a[i]);
int r=check();
if(l>r)findtwo(s,(s+e)/2);
else findtwo((s+e)/2+1,e);
}
int findlength(int x)
{
//cout<<x<<endl;
if(x==point)
{
return 0;
}
else
{
sumlength++;
findlength(father[x][0]);
}
}
int findans(int x)
{
if(length==sumlength)
{
if(startans==-1)startans=x;
else endans=x;
}
else
{
sumlength--;
findans(father[x][0]);
}
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
m = U.size();
amoney=A;
bmoney=B;
n=N;
for(int i=0;i<n;i++)road[i]=-1;
for(int i=0;i<m;i++)
{
map[i*2][0]=V[i];
map[i*2][1]=road[U[i]];
road[U[i]]=i*2;
map[i*2+1][0]=U[i];
map[i*2+1][1]=road[V[i]];
road[V[i]]=i*2+1;
}
for(int i=0;i<m;i++)p[i]=0;
cnt=check();
find(0,m-1);
tag[V[start]]=1;
tag[U[start]]=1;
point=U[start];
buildtree(point);
//cout<<endl;
//cout<<point<<endl;
//for(int i=1;i<=a[0];i++)cout<<a[i]<<" ";
//cout<<endl;
findtwo(1,a[0]);
findlength(trueroad);
//cout<<sumlength<<" "<<length<<" "<<trueroad<<endl;
findans(trueroad);
point=V[start];
a[0]=0;
tag[point]=1;
sumlength=0;
buildtree(point);
//cout<<endl;
//cout<<point<<endl;
//for(int i=1;i<=a[0];i++)cout<<a[i]<<" ";
//cout<<endl;
findtwo(1,a[0]);
findlength(trueroad);
//cout<<sumlength<<" "<<length<<" "<<trueroad<<endl;
findans(trueroad);
//cout<<startans<<" "<<endans<<endl;
answer(startans,endans);
}
Compilation message
highway.cpp: In function '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]=0;
~^~
highway.cpp: In function 'int buildtree(int)':
highway.cpp:56:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
highway.cpp: In function 'int findroad(int)':
highway.cpp:59:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(x==point || p[father[x][1]]==1)return 0;
~^~~~~~~
highway.cpp: In function 'int findtwo(int, int)':
highway.cpp:82:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(l==cnt)findtwo((s+e)/2+1,e);
~^~~~~
highway.cpp: In function 'int findlength(int)':
highway.cpp:91:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(x==point)
~^~~~~~~
highway.cpp: In function 'int findans(int)':
highway.cpp:105:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(startans==-1)startans=x;
~~~~~~~~^~~~
highway.cpp:113:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:119:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<n;i++)road[i]=-1;
~^~
highway.cpp:120:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<m;i++)
~^~
highway.cpp:130:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<m;i++)p[i]=0;
~^~
highway.cpp: In function 'int find(int, int)':
highway.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
highway.cpp: In function 'int findroad(int)':
highway.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
highway.cpp: In function 'int findtwo(int, int)':
highway.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
highway.cpp: In function 'int findlength(int)':
highway.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
380 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 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 |
380 KB |
Output is correct |
| 7 |
Correct |
2 ms |
360 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
368 KB |
Output is correct |
| 10 |
Correct |
2 ms |
448 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
424 KB |
Output is correct |
| 2 |
Correct |
24 ms |
1392 KB |
Output is correct |
| 3 |
Correct |
185 ms |
9540 KB |
Output is correct |
| 4 |
Incorrect |
205 ms |
9544 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
1276 KB |
Output is correct |
| 2 |
Correct |
57 ms |
2216 KB |
Output is correct |
| 3 |
Correct |
51 ms |
3328 KB |
Output is correct |
| 4 |
Correct |
136 ms |
8888 KB |
Output is correct |
| 5 |
Correct |
144 ms |
8860 KB |
Output is correct |
| 6 |
Correct |
134 ms |
9072 KB |
Output is correct |
| 7 |
Correct |
151 ms |
9152 KB |
Output is correct |
| 8 |
Correct |
144 ms |
9020 KB |
Output is correct |
| 9 |
Incorrect |
141 ms |
9104 KB |
Output is incorrect: {s, t} is wrong. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
19 ms |
1348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
1456 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
1356 KB |
Output is incorrect: {s, t} is wrong. |
| 2 |
Halted |
0 ms |
0 KB |
- |
