oj.uz

Submission #116687

# Submission time Handle Problem Language Result Execution time Memory
116687 2019-06-13T14:32:25 Z tinjyu Highway Tolls (IOI18_highway) C++14
69 / 100
 376 ms 13452 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]=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]=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]=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:148:6: warning: variable 'o' set but not used [-Wunused-but-set-variable]
  int o=startans;
      ^
highway.cpp:225:8: warning: 'endans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  answer(startans,endans);
  ~~~~~~^~~~~~~~~~~~~~~~~
highway.cpp:225:8: warning: 'startans' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:49: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 348 KB Output is correct
2 Correct 2 ms 428 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 356 KB Output is correct
5 Correct 2 ms 372 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 344 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 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 408 KB Output is correct
2 Correct 23 ms 1596 KB Output is correct
3 Correct 201 ms 11304 KB Output is correct
4 Correct 230 ms 11292 KB Output is correct
5 Correct 246 ms 11408 KB Output is correct
6 Correct 210 ms 11328 KB Output is correct
7 Correct 222 ms 11380 KB Output is correct
8 Correct 249 ms 11324 KB Output is correct
9 Correct 194 ms 11316 KB Output is correct
10 Correct 245 ms 11304 KB Output is correct
11 Correct 259 ms 10840 KB Output is correct
12 Correct 292 ms 11012 KB Output is correct
13 Correct 272 ms 11268 KB Output is correct
14 Correct 305 ms 11068 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1524 KB Output is correct
2 Correct 42 ms 2840 KB Output is correct
3 Correct 54 ms 3968 KB Output is correct
4 Correct 186 ms 10788 KB Output is correct
5 Correct 162 ms 10776 KB Output is correct
6 Correct 165 ms 11040 KB Output is correct
7 Correct 171 ms 11244 KB Output is correct
8 Correct 148 ms 10900 KB Output is correct
9 Correct 155 ms 10964 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 484 KB Output is correct
2 Correct 19 ms 1396 KB Output is correct
3 Correct 137 ms 8896 KB Output is correct
4 Correct 183 ms 11316 KB Output is correct
5 Correct 171 ms 11320 KB Output is correct
6 Correct 157 ms 11308 KB Output is correct
7 Correct 176 ms 11316 KB Output is correct
8 Correct 138 ms 11328 KB Output is correct
9 Correct 251 ms 11340 KB Output is correct
10 Correct 221 ms 11380 KB Output is correct
11 Correct 317 ms 11192 KB Output is correct
12 Correct 293 ms 10804 KB Output is correct
13 Correct 279 ms 10948 KB Output is correct
14 Correct 255 ms 10808 KB Output is correct
15 Correct 176 ms 11320 KB Output is correct
16 Correct 182 ms 11316 KB Output is correct
17 Correct 267 ms 11184 KB Output is correct
18 Correct 285 ms 11252 KB Output is correct
19 Correct 174 ms 11320 KB Output is correct
20 Correct 221 ms 11276 KB Output is correct
21 Correct 123 ms 11304 KB Output is correct
22 Correct 161 ms 11320 KB Output is correct
23 Correct 296 ms 10640 KB Output is correct
24 Correct 302 ms 10636 KB Output is correct
25 Correct 267 ms 11172 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 1584 KB Output is correct
2 Correct 43 ms 1644 KB Output is correct
3 Correct 266 ms 11804 KB Output is correct
4 Correct 320 ms 12212 KB Output is correct
5 Correct 353 ms 13424 KB Output is correct
6 Correct 366 ms 13028 KB Output is correct
7 Correct 376 ms 13144 KB Output is correct
8 Correct 357 ms 13428 KB Output is correct
9 Correct 276 ms 10084 KB Output is correct
10 Correct 255 ms 9708 KB Output is correct
11 Correct 252 ms 10764 KB Output is correct
12 Correct 359 ms 11944 KB Output is correct
13 Correct 367 ms 12528 KB Output is correct
14 Correct 347 ms 13276 KB Output is correct
15 Correct 354 ms 13452 KB Output is correct
16 Correct 280 ms 10328 KB Output is correct
17 Correct 223 ms 11328 KB Output is correct
18 Correct 243 ms 11412 KB Output is correct
19 Correct 247 ms 11364 KB Output is correct
20 Correct 242 ms 11384 KB Output is correct
21 Correct 359 ms 13440 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1664 KB Output is correct
2 Correct 29 ms 1656 KB Output is correct
3 Correct 280 ms 11324 KB Output is correct
4 Correct 260 ms 12188 KB Output is correct
5 Correct 312 ms 12144 KB Output is correct
6 Incorrect 361 ms 13388 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -