답안 #116672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
116672 2019-06-13T14:02:00 Z tinjyu 통행료 (IOI18_highway) C++14
5 / 100
339 ms 13320 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]=0;
	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;
	}
	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;
	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][0]<<" ";
			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++)
		{
			//cout<<tree[i][0]<<endl; 
			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; 
		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];
			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;
	//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<<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;
		}
		//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];
			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:123:7: warning: unused variable 'o' [-Wunused-variable]
   int o=0;
       ^
highway.cpp:141:6: warning: variable 'o' set but not used [-Wunused-but-set-variable]
  int o=startans;
      ^
highway.cpp:217:8: warning: 'endans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  answer(startans,endans);
  ~~~~~~^~~~~~~~~~~~~~~~~
highway.cpp:217:8: warning: 'startans' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:48:29: warning: 'point' may be used uninitialized in this function [-Wmaybe-uninitialized]
  long long int start=u[point];
                             ^
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 432 KB Output is correct
3 Correct 2 ms 344 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 348 KB Output is correct
7 Correct 2 ms 432 KB Output is correct
8 Correct 2 ms 296 KB Output is correct
9 Correct 2 ms 296 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 16 ms 1528 KB Output is correct
3 Correct 233 ms 11312 KB Output is correct
4 Incorrect 188 ms 11292 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 1464 KB Output is correct
2 Correct 35 ms 2716 KB Output is correct
3 Correct 71 ms 4068 KB Output is correct
4 Incorrect 156 ms 10764 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 416 KB Output is correct
2 Correct 26 ms 1396 KB Output is correct
3 Correct 165 ms 8896 KB Output is correct
4 Incorrect 165 ms 11220 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 1584 KB Output is correct
2 Correct 50 ms 1684 KB Output is correct
3 Incorrect 228 ms 11844 KB DO NOT PRINT ANYTHING TO STANDARD OUTPUT
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 1584 KB Output is correct
2 Correct 24 ms 1640 KB Output is correct
3 Correct 280 ms 11316 KB Output is correct
4 Correct 293 ms 12184 KB Output is correct
5 Correct 307 ms 12212 KB Output is correct
6 Incorrect 339 ms 13320 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -