oj.uz

Submission #116661

# Submission time Handle Problem Language Result Execution time Memory
116661 2019-06-13T12:04:29 Z tinjyu Highway Tolls (IOI18_highway) C++14
51 / 100
 299 ms 11400 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;
	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<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;
	}

	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:165:8: warning: 'endans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  answer(startans,endans);
  ~~~~~~^~~~~~~~~~~~~~~~~
highway.cpp:165:8: warning: 'startans' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:43: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 376 KB Output is correct
3 Correct 2 ms 352 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 248 KB Output is correct
6 Correct 2 ms 352 KB Output is correct
7 Correct 2 ms 296 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 360 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 3 ms 296 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 14 ms 1612 KB Output is correct
3 Correct 173 ms 11308 KB Output is correct
4 Correct 180 ms 11392 KB Output is correct
5 Correct 189 ms 11328 KB Output is correct
6 Correct 200 ms 11316 KB Output is correct
7 Correct 191 ms 11288 KB Output is correct
8 Correct 197 ms 11308 KB Output is correct
9 Correct 190 ms 11308 KB Output is correct
10 Correct 198 ms 11312 KB Output is correct
11 Correct 210 ms 10728 KB Output is correct
12 Correct 234 ms 11036 KB Output is correct
13 Correct 240 ms 11272 KB Output is correct
14 Correct 218 ms 11208 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1468 KB Output is correct
2 Correct 40 ms 2744 KB Output is correct
3 Correct 52 ms 3960 KB Output is correct
4 Correct 194 ms 10764 KB Output is correct
5 Correct 164 ms 10792 KB Output is correct
6 Correct 185 ms 11048 KB Output is correct
7 Correct 155 ms 11368 KB Output is correct
8 Correct 173 ms 10992 KB Output is correct
9 Correct 186 ms 10968 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 22 ms 1400 KB Output is correct
3 Correct 138 ms 8904 KB Output is correct
4 Correct 193 ms 11316 KB Output is correct
5 Correct 172 ms 11328 KB Output is correct
6 Correct 184 ms 11312 KB Output is correct
7 Correct 176 ms 11324 KB Output is correct
8 Correct 182 ms 11300 KB Output is correct
9 Correct 187 ms 11236 KB Output is correct
10 Correct 195 ms 11272 KB Output is correct
11 Correct 242 ms 11276 KB Output is correct
12 Correct 207 ms 11188 KB Output is correct
13 Correct 227 ms 11020 KB Output is correct
14 Correct 203 ms 10888 KB Output is correct
15 Correct 201 ms 11348 KB Output is correct
16 Correct 155 ms 11400 KB Output is correct
17 Correct 226 ms 11216 KB Output is correct
18 Correct 217 ms 11260 KB Output is correct
19 Correct 171 ms 11328 KB Output is correct
20 Correct 205 ms 11208 KB Output is correct
21 Correct 153 ms 11312 KB Output is correct
22 Correct 173 ms 11308 KB Output is correct
23 Correct 178 ms 10616 KB Output is correct
24 Correct 222 ms 10620 KB Output is correct
25 Correct 299 ms 11216 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1580 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 Incorrect 46 ms 1592 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -