Submission #26823

#	Time	Username	Problem	Language	Result	Execution time	Memory
26823		yutaka1999	007 (CEOI14_007)	C++14	100 / 100	436 ms	25444 KiB

007

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#define SIZE 200005

using namespace std;

vector <int> vec[SIZE];
vector <int> nd[SIZE];
int dist[SIZE],tp[SIZE];
int da[SIZE],db[SIZE];
int mx[SIZE];
bool use[SIZE];
int s,d,a,b;
int n,m;

void dfs(int v,int dp)
{
	use[v]=true;
	nd[dp].push_back(v);
	for(int i=0;i<vec[v].size();i++)
	{
		int to=vec[v][i];
		if(dist[to]<dist[v]&&!use[to])
		{
			dfs(to,dp+1);
		}
	}
}
void build()
{
	queue <int> que;
	que.push(a);
	memset(da,-1,sizeof(da));
	da[a]=0;
	while(!que.empty())
	{
		int v=que.front();que.pop();
		for(int i=0;i<vec[v].size();i++)
		{
			int to=vec[v][i];
			if(da[to]==-1)
			{
				da[to]=da[v]+1;
				que.push(to);
			}
		}
	}
	que.push(b);
	memset(db,-1,sizeof(db));
	db[b]=0;
	while(!que.empty())
	{
		int v=que.front();que.pop();
		for(int i=0;i<vec[v].size();i++)
		{
			int to=vec[v][i];
			if(db[to]==-1)
			{
				db[to]=db[v]+1;
				que.push(to);
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		dist[i]=min(da[i],db[i]);
		if(da[i]<db[i]) tp[i]=1;
		else if(da[i]>db[i]) tp[i]=2;
		else tp[i]=3;
		if(tp[i]==3) mx[i]=1;
		else mx[i]=0;
	}
	memset(use,false,sizeof(use));
	que.push(a);
	que.push(b);
	use[a]=use[b]=true;
	while(!que.empty())
	{
		int v=que.front();que.pop();
		for(int i=0;i<vec[v].size();i++)
		{
			int to=vec[v][i];
			if(dist[to]>dist[v])
			{
				if(tp[to]==3) mx[to]=max(mx[to],mx[v]+1);
				if(!use[to])
				{
					use[to]=true;
					que.push(to);
				}
			}
		}
	}
	memset(use,false,sizeof(use));
	dfs(d,0);
}
bool check(int X)//S win -> true 
{
	if(dist[s]+X<dist[d]) return true;
	if(dist[s]+X>dist[d]) return false;
	if(dist[s]+X==dist[d])
	{
		int ms=mx[s],md=0;
		for(int i=0;i<nd[X].size();i++)
		{
			int v=nd[X][i];
			md=max(md,mx[v]);
		}
		if(ms>0||md>0)
		{
			if(ms<md) return false;
			return true;
		}
		int td=0;
		for(int i=0;i<nd[X].size();i++)
		{
			int v=nd[X][i];
			if(tp[v]==1) td|=1;
			else td|=2;
		}
		if(td==3) return false;
		if(td==tp[s]) return true;
		return false;
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	scanf("%d %d %d %d",&s,&d,&a,&b);
	s--,d--,a--,b--;
	for(int i=0;i<m;i++)
	{
		int s,t;
		scanf("%d %d",&s,&t);s--,t--;
		vec[s].push_back(t);
		vec[t].push_back(s);
	}
	build();
	int l=-1,r=m+1;
	while(r-l>1)
	{
		int x=(l+r)/2;
		if(check(x)) l=x;
		else r=x;
	}
	printf("%d\n",l);
	return 0;
}

Compilation message (stderr)

007.cpp: In function 'void dfs(int, int)':
007.cpp:24:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vec[v].size();i++)
               ^
007.cpp: In function 'void build()':
007.cpp:42:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<vec[v].size();i++)
                ^
007.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<vec[v].size();i++)
                ^
007.cpp:84:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<vec[v].size();i++)
                ^
007.cpp: In function 'bool check(int)':
007.cpp:108:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<nd[X].size();i++)
                ^
007.cpp:119:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<nd[X].size();i++)
                ^
007.cpp:129:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
007.cpp: In function 'int main()':
007.cpp:132:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
007.cpp:133:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d",&s,&d,&a,&b);
                                  ^
007.cpp:138:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&s,&t);s--,t--;
                       ^

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70