답안 #65019

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65019	2018-08-06T12:43:35 Z	zadrga	007 (CEOI14_007)	C++14	100 / 100	475 ms	102504 KB

007

// 14.25

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1 << 27)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 200111

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

int da[maxn], db[maxn];
vector<int> adj[maxn];

void BFS(int zac, int d[]){
	for(int i = 0; i < maxn; i++)
		d[i] = INF;

	queue<int> q;
	d[zac] = 0;
	q.push(zac);
	while(!q.empty()){
		int x = q.front();
		q.pop();

		for(int v : adj[x]){
			if(d[x] + 1 < d[v]){
				d[v] = d[x] + 1;
				q.push(v);
			}
		}
	}
}

bool used[maxn];

int find_dist(int x){
	used[x] = 1;
	int ret = 0;
	for(int v : adj[x]){
		if(!used[v] && (da[v] + 1 == da[x]) && (db[v] + 1 == db[x]))
			ret = max(ret, 1 + find_dist(v));
	}
	return ret;
}

int main(){
	int n, m, agent, drnull, a, b;
	scanf("%d%d%d%d%d%d", &n, &m, &agent, &drnull, &a, &b);
	for(int i = 0; i < m; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		adj[x].pb(y);
		adj[y].pb(x);
	}

	BFS(a, da);
	BFS(b, db);

	int w1 = da[drnull] - da[agent];
	int w2 = db[drnull] - db[agent];

//	cout << w1 << "  " << w2 << endl;

	int ans;	
	if(min(w1, w2) < 0){
		printf("-1\n");
		return 0;
	}	

	if(abs(w1 - w2) == 1)
		ans = min(w1, w2);

	if(w1 == w2){
		memset(used, 0, sizeof(used));
		int dist_drnull = find_dist(drnull);

		memset(used, 0, sizeof(used));
		int dist_agent = find_dist(agent);

		if(dist_agent >= dist_drnull - w1)
			ans = w1;
		else
			ans = w1 - 1;

	}

	printf("%d\n", ans);
	return 0;
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:56:7: 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, &agent, &drnull, &a, &b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	6520 KB	Output is correct
2	Correct	8 ms	6892 KB	Output is correct
3	Correct	10 ms	6948 KB	Output is correct
4	Correct	10 ms	6948 KB	Output is correct
5	Correct	9 ms	6948 KB	Output is correct
6	Correct	11 ms	6968 KB	Output is correct
7	Correct	9 ms	6968 KB	Output is correct
8	Correct	8 ms	6968 KB	Output is correct
9	Correct	9 ms	7080 KB	Output is correct
10	Correct	9 ms	7080 KB	Output is correct
11	Correct	10 ms	7080 KB	Output is correct
12	Correct	10 ms	7156 KB	Output is correct
13	Correct	9 ms	7192 KB	Output is correct
14	Correct	10 ms	7192 KB	Output is correct
15	Correct	12 ms	7192 KB	Output is correct
16	Correct	12 ms	7192 KB	Output is correct
17	Correct	10 ms	7192 KB	Output is correct
18	Correct	9 ms	7216 KB	Output is correct
19	Correct	10 ms	7216 KB	Output is correct
20	Correct	9 ms	7352 KB	Output is correct
21	Correct	9 ms	7352 KB	Output is correct
22	Correct	9 ms	7352 KB	Output is correct
23	Correct	10 ms	7352 KB	Output is correct
24	Correct	10 ms	7352 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	9116 KB	Output is correct
2	Correct	63 ms	10492 KB	Output is correct
3	Correct	63 ms	10492 KB	Output is correct
4	Correct	51 ms	11816 KB	Output is correct
5	Correct	47 ms	11816 KB	Output is correct
6	Correct	38 ms	11920 KB	Output is correct
7	Correct	55 ms	12832 KB	Output is correct
8	Correct	40 ms	13304 KB	Output is correct
9	Correct	68 ms	14788 KB	Output is correct
10	Correct	291 ms	24296 KB	Output is correct
11	Correct	74 ms	24296 KB	Output is correct
12	Correct	117 ms	24296 KB	Output is correct
13	Correct	86 ms	24808 KB	Output is correct
14	Correct	72 ms	25164 KB	Output is correct
15	Correct	99 ms	27880 KB	Output is correct
16	Correct	102 ms	29228 KB	Output is correct
17	Correct	89 ms	30372 KB	Output is correct
18	Correct	100 ms	31872 KB	Output is correct
19	Correct	242 ms	35532 KB	Output is correct
20	Correct	388 ms	44040 KB	Output is correct
21	Correct	131 ms	44040 KB	Output is correct
22	Correct	124 ms	44356 KB	Output is correct
23	Correct	143 ms	47692 KB	Output is correct
24	Correct	163 ms	49156 KB	Output is correct
25	Correct	152 ms	50404 KB	Output is correct
26	Correct	154 ms	51976 KB	Output is correct
27	Correct	173 ms	54512 KB	Output is correct
28	Correct	173 ms	56636 KB	Output is correct
29	Correct	311 ms	60684 KB	Output is correct
30	Correct	384 ms	68572 KB	Output is correct
31	Correct	268 ms	69364 KB	Output is correct
32	Correct	199 ms	70160 KB	Output is correct
33	Correct	190 ms	72300 KB	Output is correct
34	Correct	184 ms	74740 KB	Output is correct
35	Correct	186 ms	77124 KB	Output is correct
36	Correct	214 ms	79464 KB	Output is correct
37	Correct	229 ms	81828 KB	Output is correct
38	Correct	233 ms	84408 KB	Output is correct
39	Correct	214 ms	86760 KB	Output is correct
40	Correct	268 ms	93048 KB	Output is correct
41	Correct	475 ms	102504 KB	Output is correct