답안 #449998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
449998 2021-08-02T10:40:35 Z vanic 007 (CEOI14_007) C++14
0 / 100
1000 ms 15252 KB
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
#include <cassert>
#include <set>
#include <array>

using namespace std;

const int maxn=2e5+5;

vector < int > ms[maxn];
int a, b, c, d;
bool bio[2][maxn];
int n, m;


bool provjeri(int x){
	set < array < int, 3 > > s;
	memset(bio, 0, sizeof(bio));
	s.insert({0, 0, b});
	s.insert({x, 1, a});
	array < int, 3 > y;
	while(!s.empty()){
		y=*s.begin();
		s.erase(s.begin());
		if(!y[1] && bio[1][y[2]]){
			continue;
		}
		if(!y[1] && (y[2]==c || y[2]==d)){
			return 0;
		}
		bio[y[1]][y[2]]=1;
		for(int i=0; i<(int)ms[y[2]].size(); i++){
			if(!bio[y[1]][ms[y[2]][i]]){
				bio[y[1]][ms[y[2]][i]]=1;
				s.insert({y[0]+1, y[1], ms[y[2]][i]});
			}
		}
	}
	return 1;
}

int binary(){
	int lo=-1, hi=n, mid;
	while(lo<hi){
		mid=(lo+hi+1)/2;
		if(provjeri(mid)){
			lo=mid;
		}
		else{
			hi=mid-1;
		}
	}
	return lo;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	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);
	}
	cout << binary() << '\n';
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Correct 3 ms 5324 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Incorrect 3 ms 5324 KB Output isn't correct
5 Incorrect 3 ms 5324 KB Output isn't correct
6 Correct 3 ms 5324 KB Output is correct
7 Correct 4 ms 5324 KB Output is correct
8 Incorrect 3 ms 5360 KB Output isn't correct
9 Correct 4 ms 5348 KB Output is correct
10 Correct 4 ms 5324 KB Output is correct
11 Correct 3 ms 5324 KB Output is correct
12 Incorrect 4 ms 5324 KB Output isn't correct
13 Correct 6 ms 5324 KB Output is correct
14 Incorrect 5 ms 5324 KB Output isn't correct
15 Correct 5 ms 5324 KB Output is correct
16 Incorrect 5 ms 5324 KB Output isn't correct
17 Incorrect 5 ms 5432 KB Output isn't correct
18 Incorrect 5 ms 5324 KB Output isn't correct
19 Correct 5 ms 5324 KB Output is correct
20 Correct 5 ms 5324 KB Output is correct
21 Correct 5 ms 5324 KB Output is correct
22 Correct 5 ms 5404 KB Output is correct
23 Correct 6 ms 5324 KB Output is correct
24 Incorrect 5 ms 5324 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 6712 KB Output is correct
2 Incorrect 252 ms 7244 KB Output isn't correct
3 Correct 214 ms 6840 KB Output is correct
4 Incorrect 293 ms 7312 KB Output isn't correct
5 Correct 248 ms 6712 KB Output is correct
6 Correct 211 ms 6688 KB Output is correct
7 Correct 257 ms 6860 KB Output is correct
8 Correct 226 ms 6980 KB Output is correct
9 Incorrect 222 ms 7312 KB Output isn't correct
10 Correct 410 ms 11648 KB Output is correct
11 Incorrect 734 ms 8280 KB Output isn't correct
12 Correct 802 ms 9232 KB Output is correct
13 Incorrect 248 ms 8504 KB Output isn't correct
14 Correct 379 ms 7988 KB Output is correct
15 Correct 903 ms 9056 KB Output is correct
16 Execution timed out 1053 ms 9284 KB Time limit exceeded
17 Correct 621 ms 8832 KB Output is correct
18 Incorrect 434 ms 8956 KB Output isn't correct
19 Correct 570 ms 9980 KB Output is correct
20 Incorrect 723 ms 12916 KB Output isn't correct
21 Incorrect 921 ms 10520 KB Output isn't correct
22 Correct 879 ms 9912 KB Output is correct
23 Execution timed out 1092 ms 10308 KB Time limit exceeded
24 Correct 900 ms 10308 KB Output is correct
25 Execution timed out 1016 ms 10084 KB Time limit exceeded
26 Execution timed out 1080 ms 9804 KB Time limit exceeded
27 Correct 616 ms 10428 KB Output is correct
28 Correct 626 ms 10564 KB Output is correct
29 Correct 841 ms 11188 KB Output is correct
30 Incorrect 770 ms 13320 KB Output isn't correct
31 Execution timed out 1068 ms 11164 KB Time limit exceeded
32 Execution timed out 1072 ms 10488 KB Time limit exceeded
33 Execution timed out 1090 ms 10548 KB Time limit exceeded
34 Execution timed out 1076 ms 10904 KB Time limit exceeded
35 Execution timed out 1046 ms 10584 KB Time limit exceeded
36 Incorrect 869 ms 10772 KB Output isn't correct
37 Execution timed out 1084 ms 11496 KB Time limit exceeded
38 Correct 795 ms 11376 KB Output is correct
39 Execution timed out 1078 ms 11528 KB Time limit exceeded
40 Execution timed out 1046 ms 12988 KB Time limit exceeded
41 Execution timed out 1083 ms 15252 KB Time limit exceeded