# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
40364 | 2018-01-31T12:04:44 Z | model_code | Evacuation plan (IZhO18_plan) | C++11 | 958 ms | 59040 KB |
#include <bits/stdc++.h> using namespace std; #ifdef WIN32 #define I64 "%I64d" #else #define I64 "%lld" #endif typedef long long ll; #define f first #define s second #define mp make_pair #define pb push_back #define all(s) s.begin(), s.end() #define sz(s) (int(s.size())) #define fname "a" #define MAXN 100001 #define MAXM 500005 const int INF = int(1e9); int n, m, k, qq; vector < pair<int, int> > g[MAXN]; int d[MAXN]; priority_queue < pair<int, int> > q; int ans[MAXN]; vector < pair<int, pair<int, int> > > e; unordered_set <int> u[MAXN]; int c[MAXN]; inline int getp(int v) { return c[v] == v ? v : c[v] = getp(c[v]); } int main() { #ifdef LOCAL freopen(fname".in", "r", stdin); freopen(fname".out", "w", stdout); #endif scanf("%d%d", &n, &m); for (int i = 0; i < m; ++i) { int v1, v2, cost; scanf("%d%d%d", &v1, &v2, &cost); --v1, --v2; g[v1].pb({v2, cost}); g[v2].pb({v1, cost}); } for (int i = 0; i < n; ++i) { d[i] = INF; } scanf("%d", &k); for (int i = 0; i < k; ++i) { int x; scanf("%d", &x); --x; d[x] = 0; q.push({-d[x], x}); } while(!q.empty()) { int dist = -q.top().f; int v = q.top().s; q.pop(); if (dist != d[v]) continue; for (const auto& t : g[v]) { int v2 = t.f; int cost = t.s; if (d[v2] > d[v] + cost) { d[v2] = d[v] + cost; q.push({-d[v2], v2}); } } } scanf("%d", &qq); for (int i = 0; i < qq; ++i) { int v1, v2; scanf("%d%d", &v1, &v2); --v1, --v2; u[v1].insert(i); u[v2].insert(i); } for (int i = 0; i < n; ++i) { c[i] = i; for (const auto& ed : g[i]) { e.pb(mp(min(d[i], d[ed.f]), mp(i, ed.f))); } } sort(all(e)); for (int i = sz(e) - 1; i >= 0; --i) { int cost = e[i].f; int v1 = getp(e[i].s.f); int v2 = getp(e[i].s.s); if (v1 == v2) continue; if (sz(u[v1]) < sz(u[v2])) swap(v1, v2); for (const int& ind : u[v2]) { if (u[v1].count(ind)) { ans[ind] = cost; u[v1].erase(ind); } else { u[v1].insert(ind); } } c[v2] = v1; } for (int i = 0; i < qq; ++i) { printf("%d\n", ans[i]); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 8104 KB | Output is correct |
2 | Correct | 11 ms | 8312 KB | Output is correct |
3 | Correct | 11 ms | 8440 KB | Output is correct |
4 | Correct | 9 ms | 8180 KB | Output is correct |
5 | Correct | 11 ms | 8412 KB | Output is correct |
6 | Correct | 11 ms | 8412 KB | Output is correct |
7 | Correct | 9 ms | 8184 KB | Output is correct |
8 | Correct | 9 ms | 8184 KB | Output is correct |
9 | Correct | 11 ms | 8412 KB | Output is correct |
10 | Correct | 11 ms | 8400 KB | Output is correct |
11 | Correct | 12 ms | 8440 KB | Output is correct |
12 | Correct | 10 ms | 8312 KB | Output is correct |
13 | Correct | 11 ms | 8312 KB | Output is correct |
14 | Correct | 11 ms | 8312 KB | Output is correct |
15 | Correct | 11 ms | 8412 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 8104 KB | Output is correct |
2 | Correct | 11 ms | 8312 KB | Output is correct |
3 | Correct | 11 ms | 8440 KB | Output is correct |
4 | Correct | 9 ms | 8180 KB | Output is correct |
5 | Correct | 11 ms | 8412 KB | Output is correct |
6 | Correct | 11 ms | 8412 KB | Output is correct |
7 | Correct | 9 ms | 8184 KB | Output is correct |
8 | Correct | 9 ms | 8184 KB | Output is correct |
9 | Correct | 11 ms | 8412 KB | Output is correct |
10 | Correct | 11 ms | 8400 KB | Output is correct |
11 | Correct | 12 ms | 8440 KB | Output is correct |
12 | Correct | 10 ms | 8312 KB | Output is correct |
13 | Correct | 11 ms | 8312 KB | Output is correct |
14 | Correct | 11 ms | 8312 KB | Output is correct |
15 | Correct | 11 ms | 8412 KB | Output is correct |
16 | Correct | 349 ms | 27660 KB | Output is correct |
17 | Correct | 880 ms | 50240 KB | Output is correct |
18 | Correct | 63 ms | 12896 KB | Output is correct |
19 | Correct | 251 ms | 29648 KB | Output is correct |
20 | Correct | 902 ms | 50372 KB | Output is correct |
21 | Correct | 500 ms | 36296 KB | Output is correct |
22 | Correct | 269 ms | 27924 KB | Output is correct |
23 | Correct | 892 ms | 50264 KB | Output is correct |
24 | Correct | 915 ms | 50292 KB | Output is correct |
25 | Correct | 873 ms | 50288 KB | Output is correct |
26 | Correct | 257 ms | 30188 KB | Output is correct |
27 | Correct | 262 ms | 30596 KB | Output is correct |
28 | Correct | 254 ms | 30508 KB | Output is correct |
29 | Correct | 248 ms | 30584 KB | Output is correct |
30 | Correct | 246 ms | 30740 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 8184 KB | Output is correct |
2 | Correct | 9 ms | 8184 KB | Output is correct |
3 | Correct | 9 ms | 8184 KB | Output is correct |
4 | Correct | 9 ms | 8188 KB | Output is correct |
5 | Correct | 9 ms | 8156 KB | Output is correct |
6 | Correct | 9 ms | 8184 KB | Output is correct |
7 | Correct | 9 ms | 8184 KB | Output is correct |
8 | Correct | 9 ms | 8184 KB | Output is correct |
9 | Correct | 9 ms | 8184 KB | Output is correct |
10 | Correct | 9 ms | 8184 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 268 ms | 24808 KB | Output is correct |
2 | Correct | 640 ms | 45020 KB | Output is correct |
3 | Correct | 685 ms | 44948 KB | Output is correct |
4 | Correct | 111 ms | 16872 KB | Output is correct |
5 | Correct | 658 ms | 45020 KB | Output is correct |
6 | Correct | 667 ms | 45100 KB | Output is correct |
7 | Correct | 679 ms | 45016 KB | Output is correct |
8 | Correct | 699 ms | 44984 KB | Output is correct |
9 | Correct | 698 ms | 44800 KB | Output is correct |
10 | Correct | 670 ms | 45004 KB | Output is correct |
11 | Correct | 656 ms | 45088 KB | Output is correct |
12 | Correct | 660 ms | 45012 KB | Output is correct |
13 | Correct | 665 ms | 45060 KB | Output is correct |
14 | Correct | 664 ms | 45236 KB | Output is correct |
15 | Correct | 638 ms | 45892 KB | Output is correct |
16 | Correct | 651 ms | 45080 KB | Output is correct |
17 | Correct | 667 ms | 44972 KB | Output is correct |
18 | Correct | 663 ms | 45016 KB | Output is correct |
19 | Correct | 113 ms | 16876 KB | Output is correct |
20 | Correct | 679 ms | 45024 KB | Output is correct |
21 | Correct | 616 ms | 45248 KB | Output is correct |
22 | Correct | 122 ms | 18920 KB | Output is correct |
23 | Correct | 130 ms | 17268 KB | Output is correct |
24 | Correct | 134 ms | 19052 KB | Output is correct |
25 | Correct | 127 ms | 19772 KB | Output is correct |
26 | Correct | 128 ms | 17384 KB | Output is correct |
27 | Correct | 114 ms | 16872 KB | Output is correct |
28 | Correct | 132 ms | 19068 KB | Output is correct |
29 | Correct | 111 ms | 16816 KB | Output is correct |
30 | Correct | 123 ms | 19144 KB | Output is correct |
31 | Correct | 106 ms | 16748 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 8104 KB | Output is correct |
2 | Correct | 11 ms | 8312 KB | Output is correct |
3 | Correct | 11 ms | 8440 KB | Output is correct |
4 | Correct | 9 ms | 8180 KB | Output is correct |
5 | Correct | 11 ms | 8412 KB | Output is correct |
6 | Correct | 11 ms | 8412 KB | Output is correct |
7 | Correct | 9 ms | 8184 KB | Output is correct |
8 | Correct | 9 ms | 8184 KB | Output is correct |
9 | Correct | 11 ms | 8412 KB | Output is correct |
10 | Correct | 11 ms | 8400 KB | Output is correct |
11 | Correct | 12 ms | 8440 KB | Output is correct |
12 | Correct | 10 ms | 8312 KB | Output is correct |
13 | Correct | 11 ms | 8312 KB | Output is correct |
14 | Correct | 11 ms | 8312 KB | Output is correct |
15 | Correct | 11 ms | 8412 KB | Output is correct |
16 | Correct | 349 ms | 27660 KB | Output is correct |
17 | Correct | 880 ms | 50240 KB | Output is correct |
18 | Correct | 63 ms | 12896 KB | Output is correct |
19 | Correct | 251 ms | 29648 KB | Output is correct |
20 | Correct | 902 ms | 50372 KB | Output is correct |
21 | Correct | 500 ms | 36296 KB | Output is correct |
22 | Correct | 269 ms | 27924 KB | Output is correct |
23 | Correct | 892 ms | 50264 KB | Output is correct |
24 | Correct | 915 ms | 50292 KB | Output is correct |
25 | Correct | 873 ms | 50288 KB | Output is correct |
26 | Correct | 257 ms | 30188 KB | Output is correct |
27 | Correct | 262 ms | 30596 KB | Output is correct |
28 | Correct | 254 ms | 30508 KB | Output is correct |
29 | Correct | 248 ms | 30584 KB | Output is correct |
30 | Correct | 246 ms | 30740 KB | Output is correct |
31 | Correct | 9 ms | 8184 KB | Output is correct |
32 | Correct | 9 ms | 8184 KB | Output is correct |
33 | Correct | 9 ms | 8184 KB | Output is correct |
34 | Correct | 9 ms | 8188 KB | Output is correct |
35 | Correct | 9 ms | 8156 KB | Output is correct |
36 | Correct | 9 ms | 8184 KB | Output is correct |
37 | Correct | 9 ms | 8184 KB | Output is correct |
38 | Correct | 9 ms | 8184 KB | Output is correct |
39 | Correct | 9 ms | 8184 KB | Output is correct |
40 | Correct | 9 ms | 8184 KB | Output is correct |
41 | Correct | 268 ms | 24808 KB | Output is correct |
42 | Correct | 640 ms | 45020 KB | Output is correct |
43 | Correct | 685 ms | 44948 KB | Output is correct |
44 | Correct | 111 ms | 16872 KB | Output is correct |
45 | Correct | 658 ms | 45020 KB | Output is correct |
46 | Correct | 667 ms | 45100 KB | Output is correct |
47 | Correct | 679 ms | 45016 KB | Output is correct |
48 | Correct | 699 ms | 44984 KB | Output is correct |
49 | Correct | 698 ms | 44800 KB | Output is correct |
50 | Correct | 670 ms | 45004 KB | Output is correct |
51 | Correct | 656 ms | 45088 KB | Output is correct |
52 | Correct | 660 ms | 45012 KB | Output is correct |
53 | Correct | 665 ms | 45060 KB | Output is correct |
54 | Correct | 664 ms | 45236 KB | Output is correct |
55 | Correct | 638 ms | 45892 KB | Output is correct |
56 | Correct | 651 ms | 45080 KB | Output is correct |
57 | Correct | 667 ms | 44972 KB | Output is correct |
58 | Correct | 663 ms | 45016 KB | Output is correct |
59 | Correct | 113 ms | 16876 KB | Output is correct |
60 | Correct | 679 ms | 45024 KB | Output is correct |
61 | Correct | 616 ms | 45248 KB | Output is correct |
62 | Correct | 122 ms | 18920 KB | Output is correct |
63 | Correct | 130 ms | 17268 KB | Output is correct |
64 | Correct | 134 ms | 19052 KB | Output is correct |
65 | Correct | 127 ms | 19772 KB | Output is correct |
66 | Correct | 128 ms | 17384 KB | Output is correct |
67 | Correct | 114 ms | 16872 KB | Output is correct |
68 | Correct | 132 ms | 19068 KB | Output is correct |
69 | Correct | 111 ms | 16816 KB | Output is correct |
70 | Correct | 123 ms | 19144 KB | Output is correct |
71 | Correct | 106 ms | 16748 KB | Output is correct |
72 | Correct | 530 ms | 40228 KB | Output is correct |
73 | Correct | 863 ms | 57676 KB | Output is correct |
74 | Correct | 880 ms | 57676 KB | Output is correct |
75 | Correct | 879 ms | 57540 KB | Output is correct |
76 | Correct | 883 ms | 57692 KB | Output is correct |
77 | Correct | 893 ms | 57676 KB | Output is correct |
78 | Correct | 884 ms | 57616 KB | Output is correct |
79 | Correct | 869 ms | 57784 KB | Output is correct |
80 | Correct | 904 ms | 57688 KB | Output is correct |
81 | Correct | 885 ms | 57648 KB | Output is correct |
82 | Correct | 871 ms | 57836 KB | Output is correct |
83 | Correct | 879 ms | 57644 KB | Output is correct |
84 | Correct | 913 ms | 57636 KB | Output is correct |
85 | Correct | 932 ms | 57696 KB | Output is correct |
86 | Correct | 922 ms | 57504 KB | Output is correct |
87 | Correct | 873 ms | 57592 KB | Output is correct |
88 | Correct | 853 ms | 57560 KB | Output is correct |
89 | Correct | 316 ms | 30564 KB | Output is correct |
90 | Correct | 958 ms | 57592 KB | Output is correct |
91 | Correct | 816 ms | 58152 KB | Output is correct |
92 | Correct | 399 ms | 31628 KB | Output is correct |
93 | Correct | 521 ms | 54968 KB | Output is correct |
94 | Correct | 314 ms | 31544 KB | Output is correct |
95 | Correct | 310 ms | 31656 KB | Output is correct |
96 | Correct | 668 ms | 59040 KB | Output is correct |
97 | Correct | 369 ms | 32240 KB | Output is correct |
98 | Correct | 318 ms | 31488 KB | Output is correct |
99 | Correct | 373 ms | 32348 KB | Output is correct |
100 | Correct | 314 ms | 31568 KB | Output is correct |