oj.uz

Submission #117148

# Submission time Handle Problem Language Result Execution time Memory
117148 2019-06-15T02:05:18 Z tinjyu Highway Tolls (IOI18_highway) C++14
51 / 100
 336 ms 13672 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;
	}
	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]=0;
		for(int i=l;i<=mid;i++)p[i]=1;
		long long int tmp=check();
		if(tmp==cnt)
		{
			l=mid+1;
		}
		else 
		{
			r=mid-1;
			point=mid;
		}
	}
	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 376 KB Output is correct
2 Correct 3 ms 440 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 352 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 320 KB Output is correct
9 Correct 2 ms 352 KB Output is correct
10 Correct 2 ms 432 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 376 KB Output is correct
2 Correct 22 ms 1588 KB Output is correct
3 Correct 210 ms 11420 KB Output is correct
4 Correct 230 ms 11288 KB Output is correct
5 Correct 231 ms 11320 KB Output is correct
6 Correct 208 ms 11336 KB Output is correct
7 Correct 227 ms 11288 KB Output is correct
8 Correct 218 ms 11404 KB Output is correct
9 Correct 185 ms 11328 KB Output is correct
10 Correct 214 ms 11328 KB Output is correct
11 Correct 271 ms 10732 KB Output is correct
12 Correct 315 ms 11024 KB Output is correct
13 Correct 307 ms 11356 KB Output is correct
14 Correct 291 ms 11192 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1540 KB Output is correct
2 Correct 61 ms 2752 KB Output is correct
3 Correct 61 ms 3964 KB Output is correct
4 Correct 183 ms 10792 KB Output is correct
5 Correct 202 ms 10780 KB Output is correct
6 Correct 169 ms 11132 KB Output is correct
7 Correct 178 ms 11248 KB Output is correct
8 Correct 157 ms 10896 KB Output is correct
9 Correct 178 ms 10952 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 25 ms 1396 KB Output is correct
3 Correct 138 ms 8904 KB Output is correct
4 Correct 221 ms 11320 KB Output is correct
5 Correct 192 ms 11328 KB Output is correct
6 Correct 176 ms 11308 KB Output is correct
7 Correct 190 ms 11324 KB Output is correct
8 Correct 181 ms 11332 KB Output is correct
9 Correct 264 ms 11220 KB Output is correct
10 Correct 214 ms 11296 KB Output is correct
11 Correct 262 ms 11380 KB Output is correct
12 Correct 304 ms 11108 KB Output is correct
13 Correct 240 ms 11008 KB Output is correct
14 Correct 279 ms 10856 KB Output is correct
15 Correct 163 ms 11312 KB Output is correct
16 Correct 170 ms 11316 KB Output is correct
17 Correct 283 ms 11196 KB Output is correct
18 Correct 274 ms 11372 KB Output is correct
19 Correct 174 ms 11324 KB Output is correct
20 Correct 224 ms 11244 KB Output is correct
21 Correct 169 ms 11428 KB Output is correct
22 Correct 170 ms 11328 KB Output is correct
23 Correct 251 ms 10712 KB Output is correct
24 Correct 300 ms 10636 KB Output is correct
25 Correct 313 ms 11200 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1584 KB Output is correct
2 Correct 43 ms 1728 KB Output is correct
3 Correct 266 ms 11892 KB Output is correct
4 Correct 317 ms 12308 KB Output is correct
5 Correct 336 ms 13072 KB Output is correct
6 Incorrect 240 ms 13672 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1584 KB Output is correct
2 Correct 24 ms 1644 KB Output is correct
3 Correct 278 ms 11420 KB Output is correct
4 Incorrect 285 ms 12212 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -