# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
65019 | 2018-08-06T12:43:35 Z | zadrga | 007 (CEOI14_007) | C++14 | 475 ms | 102504 KB |
// 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
# | Verdict | Execution time | Memory | 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 |
# | Verdict | Execution time | Memory | 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 |