oj.uz

Submission #25711

# Submission time Handle Problem Language Result Execution time Memory
25711 2017-06-23T19:00:43 Z gs14004 007 (CEOI14_007) C++11
100 / 100
 413 ms 18368 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

vector<int> graph[200005];

int n, m, s, e, a, b;
int da[200005], db[200005];
bool vis[200005];

queue<int> q;

void bfs(int s, int *d){
	memset(vis,0,sizeof(vis));
	vis[s] = 1;
	q.push(s);
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(auto &i : graph[x]){
			if(!vis[i]){
				d[i] = d[x] + 1;
				vis[i] = 1;
				q.push(i);
			}
		}
	}
}

int bfs2(int x){
	memset(vis,0,sizeof(vis));
	vis[x] = 1;
	q.push(x);
	int tmp = da[x], ret = 0;
	while(!q.empty()){
		int x = q.front();
		ret = max(ret, tmp - da[x]);
		q.pop();
		for(auto &i : graph[x]){
			if(!vis[i] && da[i] == da[x] - 1 && db[i] == db[x] - 1){
				vis[i] = 1;
				q.push(i);
			}
		}
	}
	return ret;
}

int main(){
	scanf("%d %d %d %d %d %d",&n,&m,&s,&e,&a,&b);
	for(int i=0; i<m; i++){
		int s, e;
		scanf("%d %d",&s,&e);
		graph[s].push_back(e);
		graph[e].push_back(s);
	}
	bfs(a, da);
	bfs(b, db);
	int w1 = da[e] - da[s];
	int w2 = db[e] - db[s];
	if(w1 != w2){
		printf("%d",max(min(w1, w2),-1));
	}
	else{
		int b1 = bfs2(s);
		int b2 = bfs2(e);
		printf("%d",max(w1 - (w1 + b1 < b2), -1));
	}
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:69:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d %d %d",&n,&m,&s,&e,&a,&b);
                                              ^
007.cpp:72:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&s,&e);
                       ^

Subtask #1
30.0 / 30.0

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

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 9788 KB Output is correct
2 Correct 39 ms 10316 KB Output is correct
3 Correct 29 ms 9788 KB Output is correct
4 Correct 39 ms 10448 KB Output is correct
5 Correct 43 ms 9656 KB Output is correct
6 Correct 29 ms 9920 KB Output is correct
7 Correct 29 ms 10052 KB Output is correct
8 Correct 23 ms 10052 KB Output is correct
9 Correct 46 ms 10448 KB Output is correct
10 Correct 183 ms 14672 KB Output is correct
11 Correct 66 ms 11372 KB Output is correct
12 Correct 83 ms 12032 KB Output is correct
13 Correct 83 ms 11504 KB Output is correct
14 Correct 43 ms 11108 KB Output is correct
15 Correct 79 ms 12164 KB Output is correct
16 Correct 96 ms 12296 KB Output is correct
17 Correct 76 ms 11900 KB Output is correct
18 Correct 79 ms 11900 KB Output is correct
19 Correct 156 ms 13088 KB Output is correct
20 Correct 316 ms 15860 KB Output is correct
21 Correct 133 ms 13484 KB Output is correct
22 Correct 106 ms 12824 KB Output is correct
23 Correct 123 ms 13484 KB Output is correct
24 Correct 119 ms 13352 KB Output is correct
25 Correct 99 ms 13088 KB Output is correct
26 Correct 103 ms 12824 KB Output is correct
27 Correct 119 ms 13484 KB Output is correct
28 Correct 126 ms 13484 KB Output is correct
29 Correct 189 ms 14276 KB Output is correct
30 Correct 349 ms 16388 KB Output is correct
31 Correct 139 ms 14276 KB Output is correct
32 Correct 139 ms 13484 KB Output is correct
33 Correct 129 ms 13616 KB Output is correct
34 Correct 159 ms 13880 KB Output is correct
35 Correct 133 ms 13616 KB Output is correct
36 Correct 153 ms 13880 KB Output is correct
37 Correct 146 ms 14540 KB Output is correct
38 Correct 159 ms 14408 KB Output is correct
39 Correct 166 ms 14408 KB Output is correct
40 Correct 239 ms 16124 KB Output is correct
41 Correct 413 ms 18368 KB Output is correct