oj.uz

Submission #116673

# Submission time Handle Problem Language Result Execution time Memory
116673 2019-06-13T14:03:03 Z tinjyu Highway Tolls (IOI18_highway) C++14
51 / 100
 376 ms 13528 KB 
#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];
                             ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 344 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 352 KB Output is correct
6 Correct 2 ms 440 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 2 ms 356 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 492 KB Output is correct
2 Correct 24 ms 1548 KB Output is correct
3 Correct 244 ms 11360 KB Output is correct
4 Correct 241 ms 11364 KB Output is correct
5 Correct 242 ms 11348 KB Output is correct
6 Correct 255 ms 11324 KB Output is correct
7 Correct 239 ms 11316 KB Output is correct
8 Correct 247 ms 11408 KB Output is correct
9 Correct 228 ms 11320 KB Output is correct
10 Correct 253 ms 11304 KB Output is correct
11 Correct 274 ms 10816 KB Output is correct
12 Correct 311 ms 11020 KB Output is correct
13 Correct 274 ms 11276 KB Output is correct
14 Correct 261 ms 11000 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1528 KB Output is correct
2 Correct 42 ms 2756 KB Output is correct
3 Correct 51 ms 3996 KB Output is correct
4 Correct 176 ms 10820 KB Output is correct
5 Correct 167 ms 10796 KB Output is correct
6 Correct 178 ms 11040 KB Output is correct
7 Correct 155 ms 11256 KB Output is correct
8 Correct 177 ms 11016 KB Output is correct
9 Correct 164 ms 10952 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 424 KB Output is correct
2 Correct 17 ms 1416 KB Output is correct
3 Correct 170 ms 8904 KB Output is correct
4 Correct 189 ms 11424 KB Output is correct
5 Correct 234 ms 11352 KB Output is correct
6 Correct 239 ms 11428 KB Output is correct
7 Correct 244 ms 11316 KB Output is correct
8 Correct 223 ms 11316 KB Output is correct
9 Correct 265 ms 11228 KB Output is correct
10 Correct 296 ms 11288 KB Output is correct
11 Correct 308 ms 11192 KB Output is correct
12 Correct 324 ms 10940 KB Output is correct
13 Correct 272 ms 10968 KB Output is correct
14 Correct 268 ms 10860 KB Output is correct
15 Correct 208 ms 11336 KB Output is correct
16 Correct 238 ms 11324 KB Output is correct
17 Correct 288 ms 11184 KB Output is correct
18 Correct 274 ms 11452 KB Output is correct
19 Correct 231 ms 11428 KB Output is correct
20 Correct 220 ms 11264 KB Output is correct
21 Correct 196 ms 11436 KB Output is correct
22 Correct 232 ms 11312 KB Output is correct
23 Correct 230 ms 10680 KB Output is correct
24 Correct 272 ms 10728 KB Output is correct
25 Correct 296 ms 11180 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1576 KB Output is correct
2 Correct 20 ms 1688 KB Output is correct
3 Correct 287 ms 11912 KB Output is correct
4 Correct 355 ms 12200 KB Output is correct
5 Correct 305 ms 13424 KB Output is correct
6 Correct 372 ms 13108 KB Output is correct
7 Correct 299 ms 13136 KB Output is correct
8 Correct 335 ms 13528 KB Output is correct
9 Incorrect 311 ms 10080 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1584 KB Output is correct
2 Correct 18 ms 1640 KB Output is correct
3 Correct 279 ms 11312 KB Output is correct
4 Correct 271 ms 12288 KB Output is correct
5 Correct 328 ms 12220 KB Output is correct
6 Incorrect 376 ms 13300 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -