답안 #450117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
450117	2021-08-02T11:31:51 Z	vanic	007 (CEOI14_007)	C++14	30 / 100	1000 ms	16504 KB

007

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
 
using namespace std;
 
const int maxn=2e5+5;
 
vector < int > ms[maxn];
int dist[2][maxn];
bool bio[2][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]);
			}
		}
	}
}

void siri(int x, int y, int z){
	bio[y][z][x]=1;
	for(int i=0; i<(int)ms[x].size(); i++){
		if(dist[y][ms[x][i]]==dist[y][x]-1){
			siri(ms[x][i], y, z);
		}
	}
}
 
int main(){
	memset(dist, -1, sizeof(dist));
	int n, m;
	scanf("%d%d", &n, &m);
	int a, b, c, d;
	scanf("%d%d%d%d", &a, &b, &c, &d);
	a--; b--; c--; d--;
	int x, y;
	for(int i=0; i<m; i++){
		scanf("%d%d", &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]){
		printf("-1\n");
	}
	else{
		if(dist[0][c]-dist[1][c]==dist[0][d]-dist[1][d]){
			siri(c, 0, 0);
			siri(d, 0, 1);
			siri(c, 1, 0);
			siri(d, 1, 1);
			int mini[2]={(int)1e9, (int)1e9};
			int cvor[2];
			int val;
			for(int j=0; j<2; j++){
				for(int i=0; i<n; i++){
					if(bio[j][0][i] && bio[j][1][i]){
						val=dist[j][c]-dist[j][i];
						if(val<mini[j]){
							mini[j]=val;
							cvor[j]=i;
						}
						
					}
				}
			}
			int raz=dist[1][c]-dist[0][c];
			if(cvor[0]==cvor[1]){
				printf("%d\n", raz);
			}
			else{
				if(mini[0]<=mini[1]){
					printf("%d\n", raz);
				}
				else{
					printf("%d\n", raz-1);
				}
			}
		}
		else{
			printf("%d\n", min(dist[1][c]-dist[0][c], dist[1][d]-dist[0][d]));
		}
	}
	return 0;
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
007.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d%d%d%d", &a, &b, &c, &d);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6476 KB	Output is correct
2	Correct	3 ms	6476 KB	Output is correct
3	Correct	4 ms	6476 KB	Output is correct
4	Correct	3 ms	6476 KB	Output is correct
5	Correct	4 ms	6476 KB	Output is correct
6	Correct	5 ms	6476 KB	Output is correct
7	Correct	4 ms	6476 KB	Output is correct
8	Correct	5 ms	6476 KB	Output is correct
9	Correct	4 ms	6476 KB	Output is correct
10	Correct	4 ms	6476 KB	Output is correct
11	Correct	5 ms	6476 KB	Output is correct
12	Correct	4 ms	6476 KB	Output is correct
13	Correct	4 ms	6476 KB	Output is correct
14	Correct	4 ms	6476 KB	Output is correct
15	Correct	4 ms	6476 KB	Output is correct
16	Correct	6 ms	6476 KB	Output is correct
17	Correct	4 ms	6476 KB	Output is correct
18	Correct	4 ms	6476 KB	Output is correct
19	Correct	4 ms	6548 KB	Output is correct
20	Correct	4 ms	6476 KB	Output is correct
21	Correct	5 ms	6476 KB	Output is correct
22	Correct	4 ms	6476 KB	Output is correct
23	Correct	4 ms	6476 KB	Output is correct
24	Correct	10 ms	6604 KB	Output is correct

Subtask #2

0.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	25 ms	7892 KB	Output is correct
2	Correct	49 ms	9024 KB	Output is correct
3	Correct	29 ms	8012 KB	Output is correct
4	Correct	44 ms	9124 KB	Output is correct
5	Correct	28 ms	7648 KB	Output is correct
6	Correct	26 ms	7908 KB	Output is correct
7	Correct	29 ms	8204 KB	Output is correct
8	Correct	37 ms	8156 KB	Output is correct
9	Execution timed out	1069 ms	8516 KB	Time limit exceeded
10	Execution timed out	1078 ms	12740 KB	Time limit exceeded
11	Correct	66 ms	9776 KB	Output is correct
12	Correct	87 ms	10488 KB	Output is correct
13	Correct	58 ms	9964 KB	Output is correct
14	Correct	44 ms	9024 KB	Output is correct
15	Correct	67 ms	10756 KB	Output is correct
16	Correct	79 ms	10288 KB	Output is correct
17	Correct	60 ms	10392 KB	Output is correct
18	Correct	68 ms	10284 KB	Output is correct
19	Execution timed out	1079 ms	11240 KB	Time limit exceeded
20	Execution timed out	1093 ms	14020 KB	Time limit exceeded
21	Correct	120 ms	13496 KB	Output is correct
22	Correct	103 ms	11388 KB	Output is correct
23	Correct	134 ms	13276 KB	Output is correct
24	Correct	99 ms	13100 KB	Output is correct
25	Correct	104 ms	11808 KB	Output is correct
26	Correct	99 ms	11628 KB	Output is correct
27	Correct	115 ms	12204 KB	Output is correct
28	Correct	129 ms	12168 KB	Output is correct
29	Execution timed out	1093 ms	12496 KB	Time limit exceeded
30	Execution timed out	1090 ms	14496 KB	Time limit exceeded
31	Correct	138 ms	14716 KB	Output is correct
32	Correct	123 ms	12084 KB	Output is correct
33	Correct	117 ms	12472 KB	Output is correct
34	Correct	150 ms	12612 KB	Output is correct
35	Correct	124 ms	13656 KB	Output is correct
36	Correct	126 ms	14348 KB	Output is correct
37	Correct	121 ms	12624 KB	Output is correct
38	Correct	126 ms	13320 KB	Output is correct
39	Correct	125 ms	13212 KB	Output is correct
40	Execution timed out	1078 ms	14316 KB	Time limit exceeded
41	Execution timed out	1086 ms	16504 KB	Time limit exceeded