Submission #449966

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
449966	2021-08-02T10:19:42 Z	vanic	007 (CEOI14_007)	C++14	0 / 100	280 ms	17532 KB

007

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
#include <cassert>

using namespace std;

const int maxn=2e5+5;

vector < int > ms[maxn];
int dist[2][maxn];

void bfs(int x, int ind){
	queue < int > q;
	q.push(x);
	dist[ind][x]=0;
	while(!q.empty()){
		x=q.front();
		q.pop();
		for(int i=0; i<(int)ms[x].size(); i++){
			if(dist[ind][ms[x][i]]==-1){
				dist[ind][ms[x][i]]=dist[ind][x]+1;
				q.push(ms[x][i]);
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	for(int i=0; i<2; i++){
		memset(dist[i], -1, sizeof(dist[i]));
	}
	int n, m;
	cin >> n >> m;
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	a--; b--; c--; d--;
	assert(a!=b && a!=c && a!=d);
	int x, y;
	for(int i=0; i<m; i++){
		cin >> x >> y;
		x--; y--;
		ms[x].push_back(y);
		ms[y].push_back(x);
	}
	bfs(a, 0);
	bfs(b, 1);
	if(dist[0][c]>dist[1][c] || dist[0][d]>dist[1][d]){
		cout << -1 << '\n';
	}
/*	else if(dist[0][c]==dist[1][c] || dist[0][d]==dist[1][d]){
		cout << 0 << '\n';
	}*/
	else{
//		assert(0);
		cout << min(dist[1][c]-dist[0][c], dist[1][d]-dist[0][d]) << '\n';
	}
	return 0;
}

Subtask #1

0.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6476 KB	Output is correct
2	Correct	4 ms	6476 KB	Output is correct
3	Correct	4 ms	6476 KB	Output is correct
4	Incorrect	5 ms	6496 KB	Output isn't correct
5	Incorrect	4 ms	6476 KB	Output isn't correct
6	Correct	4 ms	6476 KB	Output is correct
7	Correct	5 ms	6476 KB	Output is correct
8	Incorrect	5 ms	6476 KB	Output isn't correct
9	Correct	5 ms	6476 KB	Output is correct
10	Correct	5 ms	6476 KB	Output is correct
11	Correct	5 ms	6476 KB	Output is correct
12	Incorrect	5 ms	6600 KB	Output isn't correct
13	Correct	5 ms	6604 KB	Output is correct
14	Incorrect	4 ms	6476 KB	Output isn't correct
15	Correct	4 ms	6476 KB	Output is correct
16	Incorrect	5 ms	6604 KB	Output isn't correct
17	Incorrect	5 ms	6524 KB	Output isn't correct
18	Incorrect	5 ms	6596 KB	Output isn't correct
19	Correct	4 ms	6604 KB	Output is correct
20	Correct	4 ms	6604 KB	Output is correct
21	Correct	5 ms	6476 KB	Output is correct
22	Correct	4 ms	6604 KB	Output is correct
23	Correct	4 ms	6580 KB	Output is correct
24	Incorrect	5 ms	6604 KB	Output isn't correct

Subtask #2

0.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	8268 KB	Output is correct
2	Incorrect	30 ms	8980 KB	Output isn't correct
3	Correct	25 ms	8348 KB	Output is correct
4	Incorrect	34 ms	9156 KB	Output isn't correct
5	Correct	23 ms	8268 KB	Output is correct
6	Correct	25 ms	8368 KB	Output is correct
7	Correct	37 ms	8580 KB	Output is correct
8	Correct	34 ms	8668 KB	Output is correct
9	Incorrect	39 ms	9420 KB	Output isn't correct
10	Correct	162 ms	13880 KB	Output is correct
11	Incorrect	49 ms	10376 KB	Output isn't correct
12	Correct	65 ms	11360 KB	Output is correct
13	Incorrect	59 ms	10796 KB	Output isn't correct
14	Correct	46 ms	9984 KB	Output is correct
15	Correct	63 ms	11460 KB	Output is correct
16	Correct	69 ms	11588 KB	Output is correct
17	Correct	61 ms	11232 KB	Output is correct
18	Incorrect	64 ms	11208 KB	Output isn't correct
19	Correct	112 ms	12392 KB	Output is correct
20	Incorrect	194 ms	15088 KB	Output isn't correct
21	Incorrect	92 ms	12824 KB	Output isn't correct
22	Correct	123 ms	12100 KB	Output is correct
23	Correct	97 ms	12796 KB	Output is correct
24	Correct	91 ms	12752 KB	Output is correct
25	Incorrect	87 ms	12440 KB	Output isn't correct
26	Correct	82 ms	12228 KB	Output is correct
27	Correct	113 ms	12740 KB	Output is correct
28	Correct	147 ms	12872 KB	Output is correct
29	Correct	163 ms	13540 KB	Output is correct
30	Incorrect	199 ms	15520 KB	Output isn't correct
31	Incorrect	109 ms	13596 KB	Output isn't correct
32	Correct	125 ms	12736 KB	Output is correct
33	Correct	114 ms	12988 KB	Output is correct
34	Incorrect	107 ms	13124 KB	Output isn't correct
35	Incorrect	106 ms	12976 KB	Output isn't correct
36	Incorrect	128 ms	13228 KB	Output isn't correct
37	Correct	124 ms	13828 KB	Output is correct
38	Correct	133 ms	13800 KB	Output is correct
39	Correct	139 ms	13764 KB	Output is correct
40	Incorrect	192 ms	15416 KB	Output isn't correct
41	Correct	280 ms	17532 KB	Output is correct