oj.uz

Submission #116665

# Submission time Handle Problem Language Result Execution time Memory
116665 2019-06-13T12:53:34 Z tinjyu Highway Tolls (IOI18_highway) C++14
51 / 100
 354 ms 14164 KB 
#include "highway.h"
#include <iostream>
using namespace std;

long long int sure[130005],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;
	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<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]=0;
	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]=1;
		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;
	//cout<<start<<" "<<end<<endl;
	father[start][0]=end;
	father[start][1]=point;
	father[end][0]=start;
	father[end][1]=point;
	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<<i<<" "<<tree[i][0]<<endl; 
			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++)
		{
			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();
		//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;
	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<<"建樹"<<g<<endl;
			while(p[father[g][1]]==0)
			{
				//cout<<g<<" "<<father[g][0]<<"  "; 
				p[father[g][1]]=1;
				g=father[g][0];
			}
			//cout<<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 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:178:8: warning: 'endans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  answer(startans,endans);
  ~~~~~~^~~~~~~~~~~~~~~~~
highway.cpp:178:8: warning: 'startans' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:44: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 292 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 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 436 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 376 KB Output is correct
2 Correct 32 ms 1608 KB Output is correct
3 Correct 234 ms 12048 KB Output is correct
4 Correct 258 ms 11996 KB Output is correct
5 Correct 223 ms 12132 KB Output is correct
6 Correct 259 ms 12268 KB Output is correct
7 Correct 245 ms 12012 KB Output is correct
8 Correct 252 ms 12100 KB Output is correct
9 Correct 228 ms 12112 KB Output is correct
10 Correct 283 ms 12044 KB Output is correct
11 Correct 288 ms 11532 KB Output is correct
12 Correct 303 ms 11728 KB Output is correct
13 Correct 287 ms 11984 KB Output is correct
14 Correct 235 ms 11960 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1656 KB Output is correct
2 Correct 31 ms 2864 KB Output is correct
3 Correct 56 ms 4236 KB Output is correct
4 Correct 171 ms 11472 KB Output is correct
5 Correct 180 ms 11504 KB Output is correct
6 Correct 179 ms 11732 KB Output is correct
7 Correct 165 ms 11944 KB Output is correct
8 Correct 170 ms 11708 KB Output is correct
9 Correct 155 ms 11748 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 16 ms 1476 KB Output is correct
3 Correct 165 ms 9460 KB Output is correct
4 Correct 224 ms 12044 KB Output is correct
5 Correct 204 ms 12112 KB Output is correct
6 Correct 235 ms 12036 KB Output is correct
7 Correct 209 ms 12036 KB Output is correct
8 Correct 216 ms 12092 KB Output is correct
9 Correct 225 ms 12032 KB Output is correct
10 Correct 248 ms 11996 KB Output is correct
11 Correct 240 ms 12000 KB Output is correct
12 Correct 292 ms 11824 KB Output is correct
13 Correct 308 ms 11748 KB Output is correct
14 Correct 287 ms 11552 KB Output is correct
15 Correct 235 ms 12184 KB Output is correct
16 Correct 217 ms 12060 KB Output is correct
17 Correct 275 ms 11900 KB Output is correct
18 Correct 252 ms 11976 KB Output is correct
19 Correct 190 ms 12040 KB Output is correct
20 Correct 235 ms 11928 KB Output is correct
21 Correct 212 ms 12032 KB Output is correct
22 Correct 237 ms 12036 KB Output is correct
23 Correct 265 ms 11328 KB Output is correct
24 Correct 273 ms 11340 KB Output is correct
25 Correct 308 ms 11900 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1680 KB Output is correct
2 Correct 51 ms 1740 KB Output is correct
3 Correct 279 ms 12596 KB Output is correct
4 Correct 354 ms 13088 KB Output is correct
5 Incorrect 344 ms 14164 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1676 KB Output is correct
2 Correct 21 ms 1688 KB Output is correct
3 Correct 297 ms 12132 KB Output is correct
4 Incorrect 303 ms 12952 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -