oj.uz

Submission #30009

# Submission time Handle Problem Language Result Execution time Memory
30009 2017-07-21T12:03:00 Z PrOAhMeT 007 (CEOI14_007) C++14
0 / 100
 159 ms 16280 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXN=200005;
int n,m,dis[4][MAXN],s,d,a,b,t,tt,x,y,mx,aa,mx1,dd[MAXN],tmp[MAXN];
bool vis[MAXN];
pii edge[600005];
vector<int> v[MAXN];

inline void bfs(int start,int wait,int u) {

	memset(dis[u],-1,sizeof dis[u]);
	queue<int> q;
	dis[u][start]=0;
	q.push(start);
	while(!q.empty()) {
		x=q.front();
		q.pop();
		for(int i=0;i<v[x].size();++i) {
			y=v[x][i];
			if(dis[u][y]==-1) {
				dis[u][y]=dis[u][x]+1;
				q.push(y);
			}
		}
	}

}

inline void go(int x) {

	vis[x]=1;
	mx=max(mx,dis[aa][x]);
	for(int i=0;i<v[x].size();++i) {
		y=v[x][i];
		if(dis[2][y]<dis[2][x]&&dis[3][y]<dis[3][x])
			go(y);
	}

}

int main() {

	scanf("%d %d",&n,&m);
	scanf("%d %d %d %d",&s,&d,&a,&b);
	for(int i=0;i<m;++i) {
		scanf("%d %d",&edge[i].st,&edge[i].nd);
		++dd[t];
		++dd[tt];
	}
	for(int i=1;i<=n;++i)
		v[i].resize(dd[i]);
	for(int i=0;i<m;++i) {
		x=edge[i].st;
		y=edge[i].nd;
		v[y][tmp[y]++]=x;
		v[x][tmp[x]++]=y;
	}
	int l=0,r=n,ans=-1,md;
	bfs(d,0,1);
	bfs(s,0,0);
	bfs(a,0,2);
	bfs(b,0,3);
	if(dis[0][a]>dis[1][a]||dis[0][b]>dis[1][b])
		cout<<-1<<endl;
	else if(!((dis[1][a]-dis[0][a]==dis[1][b]-dis[0][b])&&dis[0][a]==dis[0][b])){
		cout<<min(dis[1][a]-dis[0][a],dis[1][b]-dis[0][b])<<endl;
	}
	else {
		aa=0;
		go(s);
		mx1=mx;
		if(vis[a]==0||vis[b]==0) {
			memset(vis,0,sizeof vis);
			mx=0;
			aa=1;
			go(d);
			if(mx<=dis[1][a]-dis[0][a]+mx1)
				cout<<dis[1][a]-dis[0][a]<<endl;
			else cout<<dis[1][a]-dis[0][a]-1<<endl;
		}
		else cout<<dis[1][a]-dis[0][a]<<endl;
	}

}

Compilation message

007.cpp: In function 'void bfs(int, int, int)':
007.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v[x].size();++i) {
                ^
007.cpp: In function 'void go(int)':
007.cpp:41:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();++i) {
               ^
007.cpp: In function 'int main()':
007.cpp:66:6: warning: unused variable 'l' [-Wunused-variable]
  int l=0,r=n,ans=-1,md;
      ^
007.cpp:66:10: warning: unused variable 'r' [-Wunused-variable]
  int l=0,r=n,ans=-1,md;
          ^
007.cpp:66:14: warning: unused variable 'ans' [-Wunused-variable]
  int l=0,r=n,ans=-1,md;
              ^
007.cpp:66:21: warning: unused variable 'md' [-Wunused-variable]
  int l=0,r=n,ans=-1,md;
                     ^
007.cpp:51: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:52: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:54:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&edge[i].st,&edge[i].nd);
                                         ^

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 0 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 9 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 9 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 13 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 9 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 9 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 9 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 13 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 19 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 93 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 23 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 29 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 33 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 19 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 39 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 33 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 39 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 29 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 79 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 129 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 53 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 39 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 56 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 33 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 36 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 66 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 63 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 49 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 99 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 153 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 63 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 53 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 49 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 56 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 49 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 59 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 56 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 66 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 56 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 113 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 159 ms 16280 KB Execution killed with signal 11 (could be triggered by violating memory limits)