oj.uz

Submission #26823

# Submission time Handle Problem Language Result Execution time Memory
26823 2017-07-06T07:40:51 Z yutaka1999 007 (CEOI14_007) C++14
100 / 100
 436 ms 25444 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15412 KB Output is correct
2 Correct 0 ms 15412 KB Output is correct
3 Correct 0 ms 15412 KB Output is correct
4 Correct 0 ms 15412 KB Output is correct
5 Correct 0 ms 15412 KB Output is correct
6 Correct 9 ms 15412 KB Output is correct
7 Correct 3 ms 15412 KB Output is correct
8 Correct 0 ms 15412 KB Output is correct
9 Correct 3 ms 15412 KB Output is correct
10 Correct 0 ms 15412 KB Output is correct
11 Correct 0 ms 15412 KB Output is correct
12 Correct 0 ms 15412 KB Output is correct
13 Correct 0 ms 15412 KB Output is correct
14 Correct 0 ms 15412 KB Output is correct
15 Correct 0 ms 15412 KB Output is correct
16 Correct 3 ms 15412 KB Output is correct
17 Correct 3 ms 15412 KB Output is correct
18 Correct 0 ms 15412 KB Output is correct
19 Correct 0 ms 15412 KB Output is correct
20 Correct 3 ms 15412 KB Output is correct
21 Correct 0 ms 15412 KB Output is correct
22 Correct 3 ms 15412 KB Output is correct
23 Correct 0 ms 15412 KB Output is correct
24 Correct 0 ms 15412 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16732 KB Output is correct
2 Correct 53 ms 17680 KB Output is correct
3 Correct 36 ms 16864 KB Output is correct
4 Correct 56 ms 17688 KB Output is correct
5 Correct 39 ms 16600 KB Output is correct
6 Correct 36 ms 17112 KB Output is correct
7 Correct 43 ms 16996 KB Output is correct
8 Correct 43 ms 16996 KB Output is correct
9 Correct 63 ms 17392 KB Output is correct
10 Correct 273 ms 21616 KB Output is correct
11 Correct 93 ms 18316 KB Output is correct
12 Correct 116 ms 18976 KB Output is correct
13 Correct 93 ms 18448 KB Output is correct
14 Correct 96 ms 18052 KB Output is correct
15 Correct 123 ms 19240 KB Output is correct
16 Correct 116 ms 19240 KB Output is correct
17 Correct 109 ms 18844 KB Output is correct
18 Correct 116 ms 18844 KB Output is correct
19 Correct 153 ms 20164 KB Output is correct
20 Correct 336 ms 22936 KB Output is correct
21 Correct 173 ms 21760 KB Output is correct
22 Correct 153 ms 19900 KB Output is correct
23 Correct 143 ms 21408 KB Output is correct
24 Correct 149 ms 21368 KB Output is correct
25 Correct 153 ms 20296 KB Output is correct
26 Correct 113 ms 19900 KB Output is correct
27 Correct 163 ms 20428 KB Output is correct
28 Correct 193 ms 20428 KB Output is correct
29 Correct 249 ms 21484 KB Output is correct
30 Correct 303 ms 23464 KB Output is correct
31 Correct 189 ms 22836 KB Output is correct
32 Correct 169 ms 20560 KB Output is correct
33 Correct 143 ms 20692 KB Output is correct
34 Correct 209 ms 21088 KB Output is correct
35 Correct 163 ms 22064 KB Output is correct
36 Correct 139 ms 22444 KB Output is correct
37 Correct 203 ms 21664 KB Output is correct
38 Correct 216 ms 21352 KB Output is correct
39 Correct 273 ms 21352 KB Output is correct
40 Correct 343 ms 23332 KB Output is correct
41 Correct 436 ms 25444 KB Output is correct