# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
50846 | 2018-06-13T16:41:52 Z | Nicksechko | Evacuation plan (IZhO18_plan) | C++14 | 1070 ms | 57100 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 8184 KB | Output is correct |
2 | Correct | 12 ms | 8312 KB | Output is correct |
3 | Correct | 11 ms | 8440 KB | Output is correct |
4 | Correct | 11 ms | 8184 KB | Output is correct |
5 | Correct | 10 ms | 8312 KB | Output is correct |
6 | Correct | 11 ms | 8316 KB | Output is correct |
7 | Correct | 11 ms | 8184 KB | Output is correct |
8 | Correct | 11 ms | 8184 KB | Output is correct |
9 | Correct | 12 ms | 8312 KB | Output is correct |
10 | Correct | 14 ms | 8432 KB | Output is correct |
11 | Correct | 11 ms | 8440 KB | Output is correct |
12 | Correct | 11 ms | 8312 KB | Output is correct |
13 | Correct | 12 ms | 8412 KB | Output is correct |
14 | Correct | 13 ms | 8312 KB | Output is correct |
15 | Correct | 11 ms | 8312 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 8184 KB | Output is correct |
2 | Correct | 12 ms | 8312 KB | Output is correct |
3 | Correct | 11 ms | 8440 KB | Output is correct |
4 | Correct | 11 ms | 8184 KB | Output is correct |
5 | Correct | 10 ms | 8312 KB | Output is correct |
6 | Correct | 11 ms | 8316 KB | Output is correct |
7 | Correct | 11 ms | 8184 KB | Output is correct |
8 | Correct | 11 ms | 8184 KB | Output is correct |
9 | Correct | 12 ms | 8312 KB | Output is correct |
10 | Correct | 14 ms | 8432 KB | Output is correct |
11 | Correct | 11 ms | 8440 KB | Output is correct |
12 | Correct | 11 ms | 8312 KB | Output is correct |
13 | Correct | 12 ms | 8412 KB | Output is correct |
14 | Correct | 13 ms | 8312 KB | Output is correct |
15 | Correct | 11 ms | 8312 KB | Output is correct |
16 | Correct | 412 ms | 27664 KB | Output is correct |
17 | Correct | 1070 ms | 52244 KB | Output is correct |
18 | Correct | 64 ms | 12784 KB | Output is correct |
19 | Correct | 250 ms | 29892 KB | Output is correct |
20 | Correct | 901 ms | 52468 KB | Output is correct |
21 | Correct | 624 ms | 36320 KB | Output is correct |
22 | Correct | 311 ms | 27168 KB | Output is correct |
23 | Correct | 924 ms | 52900 KB | Output is correct |
24 | Correct | 912 ms | 52620 KB | Output is correct |
25 | Correct | 896 ms | 53124 KB | Output is correct |
26 | Correct | 271 ms | 29796 KB | Output is correct |
27 | Correct | 262 ms | 30076 KB | Output is correct |
28 | Correct | 268 ms | 29476 KB | Output is correct |
29 | Correct | 260 ms | 30380 KB | Output is correct |
30 | Correct | 259 ms | 30672 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 8184 KB | Output is correct |
2 | Correct | 9 ms | 8184 KB | Output is correct |
3 | Correct | 9 ms | 8256 KB | Output is correct |
4 | Correct | 9 ms | 8184 KB | Output is correct |
5 | Correct | 9 ms | 8184 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 | 10 ms | 8248 KB | Output is correct |
10 | Correct | 9 ms | 8184 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 282 ms | 24516 KB | Output is correct |
2 | Correct | 668 ms | 40600 KB | Output is correct |
3 | Correct | 693 ms | 41028 KB | Output is correct |
4 | Correct | 119 ms | 16748 KB | Output is correct |
5 | Correct | 685 ms | 41192 KB | Output is correct |
6 | Correct | 682 ms | 40980 KB | Output is correct |
7 | Correct | 692 ms | 40620 KB | Output is correct |
8 | Correct | 689 ms | 40588 KB | Output is correct |
9 | Correct | 744 ms | 40840 KB | Output is correct |
10 | Correct | 661 ms | 40848 KB | Output is correct |
11 | Correct | 679 ms | 40864 KB | Output is correct |
12 | Correct | 666 ms | 40128 KB | Output is correct |
13 | Correct | 696 ms | 40244 KB | Output is correct |
14 | Correct | 694 ms | 40360 KB | Output is correct |
15 | Correct | 685 ms | 40536 KB | Output is correct |
16 | Correct | 730 ms | 39500 KB | Output is correct |
17 | Correct | 690 ms | 39524 KB | Output is correct |
18 | Correct | 690 ms | 39388 KB | Output is correct |
19 | Correct | 118 ms | 15720 KB | Output is correct |
20 | Correct | 686 ms | 38676 KB | Output is correct |
21 | Correct | 608 ms | 38048 KB | Output is correct |
22 | Correct | 115 ms | 17756 KB | Output is correct |
23 | Correct | 133 ms | 16452 KB | Output is correct |
24 | Correct | 131 ms | 18032 KB | Output is correct |
25 | Correct | 123 ms | 18804 KB | Output is correct |
26 | Correct | 136 ms | 16492 KB | Output is correct |
27 | Correct | 114 ms | 16068 KB | Output is correct |
28 | Correct | 153 ms | 18248 KB | Output is correct |
29 | Correct | 122 ms | 15852 KB | Output is correct |
30 | Correct | 129 ms | 18236 KB | Output is correct |
31 | Correct | 119 ms | 16180 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 8184 KB | Output is correct |
2 | Correct | 12 ms | 8312 KB | Output is correct |
3 | Correct | 11 ms | 8440 KB | Output is correct |
4 | Correct | 11 ms | 8184 KB | Output is correct |
5 | Correct | 10 ms | 8312 KB | Output is correct |
6 | Correct | 11 ms | 8316 KB | Output is correct |
7 | Correct | 11 ms | 8184 KB | Output is correct |
8 | Correct | 11 ms | 8184 KB | Output is correct |
9 | Correct | 12 ms | 8312 KB | Output is correct |
10 | Correct | 14 ms | 8432 KB | Output is correct |
11 | Correct | 11 ms | 8440 KB | Output is correct |
12 | Correct | 11 ms | 8312 KB | Output is correct |
13 | Correct | 12 ms | 8412 KB | Output is correct |
14 | Correct | 13 ms | 8312 KB | Output is correct |
15 | Correct | 11 ms | 8312 KB | Output is correct |
16 | Correct | 412 ms | 27664 KB | Output is correct |
17 | Correct | 1070 ms | 52244 KB | Output is correct |
18 | Correct | 64 ms | 12784 KB | Output is correct |
19 | Correct | 250 ms | 29892 KB | Output is correct |
20 | Correct | 901 ms | 52468 KB | Output is correct |
21 | Correct | 624 ms | 36320 KB | Output is correct |
22 | Correct | 311 ms | 27168 KB | Output is correct |
23 | Correct | 924 ms | 52900 KB | Output is correct |
24 | Correct | 912 ms | 52620 KB | Output is correct |
25 | Correct | 896 ms | 53124 KB | Output is correct |
26 | Correct | 271 ms | 29796 KB | Output is correct |
27 | Correct | 262 ms | 30076 KB | Output is correct |
28 | Correct | 268 ms | 29476 KB | Output is correct |
29 | Correct | 260 ms | 30380 KB | Output is correct |
30 | Correct | 259 ms | 30672 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 | 8256 KB | Output is correct |
34 | Correct | 9 ms | 8184 KB | Output is correct |
35 | Correct | 9 ms | 8184 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 | 10 ms | 8248 KB | Output is correct |
40 | Correct | 9 ms | 8184 KB | Output is correct |
41 | Correct | 282 ms | 24516 KB | Output is correct |
42 | Correct | 668 ms | 40600 KB | Output is correct |
43 | Correct | 693 ms | 41028 KB | Output is correct |
44 | Correct | 119 ms | 16748 KB | Output is correct |
45 | Correct | 685 ms | 41192 KB | Output is correct |
46 | Correct | 682 ms | 40980 KB | Output is correct |
47 | Correct | 692 ms | 40620 KB | Output is correct |
48 | Correct | 689 ms | 40588 KB | Output is correct |
49 | Correct | 744 ms | 40840 KB | Output is correct |
50 | Correct | 661 ms | 40848 KB | Output is correct |
51 | Correct | 679 ms | 40864 KB | Output is correct |
52 | Correct | 666 ms | 40128 KB | Output is correct |
53 | Correct | 696 ms | 40244 KB | Output is correct |
54 | Correct | 694 ms | 40360 KB | Output is correct |
55 | Correct | 685 ms | 40536 KB | Output is correct |
56 | Correct | 730 ms | 39500 KB | Output is correct |
57 | Correct | 690 ms | 39524 KB | Output is correct |
58 | Correct | 690 ms | 39388 KB | Output is correct |
59 | Correct | 118 ms | 15720 KB | Output is correct |
60 | Correct | 686 ms | 38676 KB | Output is correct |
61 | Correct | 608 ms | 38048 KB | Output is correct |
62 | Correct | 115 ms | 17756 KB | Output is correct |
63 | Correct | 133 ms | 16452 KB | Output is correct |
64 | Correct | 131 ms | 18032 KB | Output is correct |
65 | Correct | 123 ms | 18804 KB | Output is correct |
66 | Correct | 136 ms | 16492 KB | Output is correct |
67 | Correct | 114 ms | 16068 KB | Output is correct |
68 | Correct | 153 ms | 18248 KB | Output is correct |
69 | Correct | 122 ms | 15852 KB | Output is correct |
70 | Correct | 129 ms | 18236 KB | Output is correct |
71 | Correct | 119 ms | 16180 KB | Output is correct |
72 | Correct | 563 ms | 36796 KB | Output is correct |
73 | Correct | 924 ms | 50164 KB | Output is correct |
74 | Correct | 1027 ms | 50448 KB | Output is correct |
75 | Correct | 952 ms | 50992 KB | Output is correct |
76 | Correct | 947 ms | 50872 KB | Output is correct |
77 | Correct | 947 ms | 50840 KB | Output is correct |
78 | Correct | 1028 ms | 51168 KB | Output is correct |
79 | Correct | 940 ms | 50288 KB | Output is correct |
80 | Correct | 926 ms | 49752 KB | Output is correct |
81 | Correct | 926 ms | 49980 KB | Output is correct |
82 | Correct | 952 ms | 49400 KB | Output is correct |
83 | Correct | 943 ms | 48840 KB | Output is correct |
84 | Correct | 1040 ms | 48584 KB | Output is correct |
85 | Correct | 931 ms | 49024 KB | Output is correct |
86 | Correct | 975 ms | 48884 KB | Output is correct |
87 | Correct | 961 ms | 48692 KB | Output is correct |
88 | Correct | 939 ms | 49804 KB | Output is correct |
89 | Correct | 341 ms | 28696 KB | Output is correct |
90 | Correct | 953 ms | 49808 KB | Output is correct |
91 | Correct | 892 ms | 49716 KB | Output is correct |
92 | Correct | 355 ms | 29792 KB | Output is correct |
93 | Correct | 556 ms | 53164 KB | Output is correct |
94 | Correct | 337 ms | 29020 KB | Output is correct |
95 | Correct | 318 ms | 30132 KB | Output is correct |
96 | Correct | 627 ms | 57100 KB | Output is correct |
97 | Correct | 373 ms | 30484 KB | Output is correct |
98 | Correct | 322 ms | 29924 KB | Output is correct |
99 | Correct | 362 ms | 30888 KB | Output is correct |
100 | Correct | 328 ms | 30344 KB | Output is correct |