oj.uz

Submission #116662

# Submission time Handle Problem Language Result Execution time Memory
116662 2019-06-13T12:21:06 Z tinjyu Highway Tolls (IOI18_highway) C++14
51 / 100
 280 ms 14340 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]=sure[i];
	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]=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=l;i<=mid;i++)p[i]=0;
		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;
	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++;
	}	
	for(int i=1;i<=tree[0][0];i++)
	{
		int g=tree[i][0];
		//cout<<tree[i][0]<<" "; 
		while(p[father[g][1]]==1)
		{
			p[father[g][1]]=0;
			g=father[g][0];
		}
	}
	//cout<<endl;
	cnt=check();
	l=1,r=tree[0][0];
	int startans;
	while(l<=r)
	{
		int mid=(l+r)/2;
		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();
		if(tmp==cnt)
		{
			startans=tree[mid][0];
			r=mid-1;
		}
		else l=mid+1;
	}
	int o=startans;
	while(sure[father[o][1]]==1)
	{
		//cout<<u[father[o][1]]<<" "<<v[father[o][1]]<<endl;
		sure[father[o][1]]=0;
		p[father[o][1]]=0;
		o=father[o][0];
	}
	for(int i=1;i<=tree[0][1];i++)
	{
		int g=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;
	}
	//for(int i=0;i<m;i++)cout<<p[i]<<" ";
	//cout<<endl;
	cnt=check();
	//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=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:173:8: warning: 'endans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  answer(startans,endans);
  ~~~~~~^~~~~~~~~~~~~~~~~
highway.cpp:119:24: warning: 'startans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  while(sure[father[o][1]]==1)
             ~~~~~~~~~~~^
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 356 KB Output is correct
2 Correct 2 ms 352 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 352 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 380 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 504 KB Output is correct
2 Correct 42 ms 1612 KB Output is correct
3 Correct 161 ms 12060 KB Output is correct
4 Correct 241 ms 12000 KB Output is correct
5 Correct 193 ms 12028 KB Output is correct
6 Correct 175 ms 12020 KB Output is correct
7 Correct 169 ms 12016 KB Output is correct
8 Correct 184 ms 12028 KB Output is correct
9 Correct 174 ms 12124 KB Output is correct
10 Correct 192 ms 12032 KB Output is correct
11 Correct 194 ms 11440 KB Output is correct
12 Correct 230 ms 11748 KB Output is correct
13 Correct 228 ms 11976 KB Output is correct
14 Correct 211 ms 12016 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1528 KB Output is correct
2 Correct 42 ms 2916 KB Output is correct
3 Correct 56 ms 4204 KB Output is correct
4 Correct 182 ms 11588 KB Output is correct
5 Correct 170 ms 11508 KB Output is correct
6 Correct 194 ms 11840 KB Output is correct
7 Correct 196 ms 12040 KB Output is correct
8 Correct 173 ms 11628 KB Output is correct
9 Correct 162 ms 11792 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 18 ms 1576 KB Output is correct
3 Correct 138 ms 9524 KB Output is correct
4 Correct 162 ms 12028 KB Output is correct
5 Correct 190 ms 12128 KB Output is correct
6 Correct 195 ms 12024 KB Output is correct
7 Correct 155 ms 12024 KB Output is correct
8 Correct 183 ms 12064 KB Output is correct
9 Correct 201 ms 12020 KB Output is correct
10 Correct 198 ms 11996 KB Output is correct
11 Correct 257 ms 12012 KB Output is correct
12 Correct 233 ms 11808 KB Output is correct
13 Correct 209 ms 11728 KB Output is correct
14 Correct 248 ms 11580 KB Output is correct
15 Correct 208 ms 12016 KB Output is correct
16 Correct 172 ms 12128 KB Output is correct
17 Correct 269 ms 11888 KB Output is correct
18 Correct 243 ms 11980 KB Output is correct
19 Correct 203 ms 12024 KB Output is correct
20 Correct 185 ms 11980 KB Output is correct
21 Correct 172 ms 12044 KB Output is correct
22 Correct 144 ms 12044 KB Output is correct
23 Correct 226 ms 11320 KB Output is correct
24 Correct 228 ms 11452 KB Output is correct
25 Correct 256 ms 11924 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 1672 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1592 KB Output is correct
2 Correct 37 ms 1688 KB Output is correct
3 Correct 207 ms 12116 KB Output is correct
4 Correct 228 ms 13000 KB Output is correct
5 Partially correct 247 ms 13052 KB Output is partially correct
6 Incorrect 280 ms 14340 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -