# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
133427 | 2019-07-20T15:14:47 Z | Kastanda | Evacuation plan (IZhO18_plan) | C++11 | 651 ms | 26100 KB |
// ItnoE #include<bits/stdc++.h> using namespace std; const int N = 100005; int n, m, q, k, D[N], P[N], S[N], R[N]; vector < pair < int , int > > Adj[N]; vector < pair < int , int > > Q[N]; inline bool CMP(int i, int j) { return (D[i] > D[j]); } int Find(int v) { return (P[v] < 0 ? v : (P[v] = Find(P[v]))); } inline void Merge(int v, int u, int w) { v = Find(v); u = Find(u); if (v == u) return ; if (Q[v].size() < Q[u].size()) swap(v, u); for (auto X : Q[u]) if (Find(X.first) == v) R[X.second] = w; else Q[v].push_back(X); Q[u].clear(); P[u] = v; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i ++) { int v, u, w; scanf("%d%d%d", &v, &u, &w); Adj[v].push_back({u, w}); Adj[u].push_back({v, w}); } memset(D, 63, sizeof(D)); priority_queue < pair < int , int > > Pq; scanf("%d", &k); for (int v; k; k --) scanf("%d", &v), D[v] = 0, Pq.push({0, v}); while (Pq.size()) { int v = Pq.top().second; int d = - Pq.top().first; Pq.pop(); if (d > D[v]) continue; for (auto u : Adj[v]) if (D[u.first] > D[v] + u.second) D[u.first] = D[v] + u.second, Pq.push({-D[u.first], u.first}); } scanf("%d", &q); for (int i = 1; i <= q; i ++) { int v, u; scanf("%d%d", &v, &u); Q[v].push_back({u, i}); Q[u].push_back({v, i}); } memset(P, -1, sizeof(P)); iota(S, S + n + 1, 0); sort(S + 1, S + n + 1, CMP); for (int j = 1; j <= n; j ++) { int v = S[j]; for (auto u : Adj[v]) if (D[u.first] >= D[v]) Merge(v, u.first, D[v]); } for (int i = 1; i <= q; i ++) printf("%d\n", R[i]); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5752 KB | Output is correct |
2 | Correct | 7 ms | 5880 KB | Output is correct |
3 | Correct | 7 ms | 5880 KB | Output is correct |
4 | Correct | 6 ms | 5752 KB | Output is correct |
5 | Correct | 8 ms | 5940 KB | Output is correct |
6 | Correct | 8 ms | 5880 KB | Output is correct |
7 | Correct | 7 ms | 5752 KB | Output is correct |
8 | Correct | 7 ms | 5880 KB | Output is correct |
9 | Correct | 8 ms | 5880 KB | Output is correct |
10 | Correct | 8 ms | 5880 KB | Output is correct |
11 | Correct | 8 ms | 5880 KB | Output is correct |
12 | Correct | 8 ms | 5880 KB | Output is correct |
13 | Correct | 8 ms | 5880 KB | Output is correct |
14 | Correct | 8 ms | 5880 KB | Output is correct |
15 | Correct | 8 ms | 5880 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5752 KB | Output is correct |
2 | Correct | 7 ms | 5880 KB | Output is correct |
3 | Correct | 7 ms | 5880 KB | Output is correct |
4 | Correct | 6 ms | 5752 KB | Output is correct |
5 | Correct | 8 ms | 5940 KB | Output is correct |
6 | Correct | 8 ms | 5880 KB | Output is correct |
7 | Correct | 7 ms | 5752 KB | Output is correct |
8 | Correct | 7 ms | 5880 KB | Output is correct |
9 | Correct | 8 ms | 5880 KB | Output is correct |
10 | Correct | 8 ms | 5880 KB | Output is correct |
11 | Correct | 8 ms | 5880 KB | Output is correct |
12 | Correct | 8 ms | 5880 KB | Output is correct |
13 | Correct | 8 ms | 5880 KB | Output is correct |
14 | Correct | 8 ms | 5880 KB | Output is correct |
15 | Correct | 8 ms | 5880 KB | Output is correct |
16 | Correct | 212 ms | 15496 KB | Output is correct |
17 | Correct | 572 ms | 25836 KB | Output is correct |
18 | Correct | 42 ms | 7672 KB | Output is correct |
19 | Correct | 172 ms | 15656 KB | Output is correct |
20 | Correct | 592 ms | 25896 KB | Output is correct |
21 | Correct | 316 ms | 18800 KB | Output is correct |
22 | Correct | 186 ms | 14696 KB | Output is correct |
23 | Correct | 651 ms | 25888 KB | Output is correct |
24 | Correct | 596 ms | 25848 KB | Output is correct |
25 | Correct | 619 ms | 25920 KB | Output is correct |
26 | Correct | 168 ms | 15528 KB | Output is correct |
27 | Correct | 174 ms | 15548 KB | Output is correct |
28 | Correct | 172 ms | 15336 KB | Output is correct |
29 | Correct | 174 ms | 15468 KB | Output is correct |
30 | Correct | 175 ms | 15720 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 5728 KB | Output is correct |
2 | Correct | 6 ms | 5752 KB | Output is correct |
3 | Correct | 7 ms | 5880 KB | Output is correct |
4 | Correct | 7 ms | 5752 KB | Output is correct |
5 | Correct | 7 ms | 5752 KB | Output is correct |
6 | Correct | 7 ms | 5752 KB | Output is correct |
7 | Correct | 6 ms | 5752 KB | Output is correct |
8 | Correct | 6 ms | 5748 KB | Output is correct |
9 | Correct | 8 ms | 5752 KB | Output is correct |
10 | Correct | 7 ms | 5752 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 233 ms | 13268 KB | Output is correct |
2 | Correct | 489 ms | 21480 KB | Output is correct |
3 | Correct | 572 ms | 21432 KB | Output is correct |
4 | Correct | 106 ms | 9336 KB | Output is correct |
5 | Correct | 513 ms | 21360 KB | Output is correct |
6 | Correct | 504 ms | 21484 KB | Output is correct |
7 | Correct | 503 ms | 21392 KB | Output is correct |
8 | Correct | 496 ms | 21396 KB | Output is correct |
9 | Correct | 491 ms | 21408 KB | Output is correct |
10 | Correct | 493 ms | 21340 KB | Output is correct |
11 | Correct | 494 ms | 21304 KB | Output is correct |
12 | Correct | 519 ms | 21360 KB | Output is correct |
13 | Correct | 512 ms | 21268 KB | Output is correct |
14 | Correct | 568 ms | 21484 KB | Output is correct |
15 | Correct | 506 ms | 21736 KB | Output is correct |
16 | Correct | 493 ms | 21484 KB | Output is correct |
17 | Correct | 475 ms | 21336 KB | Output is correct |
18 | Correct | 480 ms | 21272 KB | Output is correct |
19 | Correct | 107 ms | 9336 KB | Output is correct |
20 | Correct | 519 ms | 21456 KB | Output is correct |
21 | Correct | 486 ms | 20976 KB | Output is correct |
22 | Correct | 104 ms | 10988 KB | Output is correct |
23 | Correct | 108 ms | 9912 KB | Output is correct |
24 | Correct | 112 ms | 11060 KB | Output is correct |
25 | Correct | 107 ms | 10988 KB | Output is correct |
26 | Correct | 112 ms | 10104 KB | Output is correct |
27 | Correct | 97 ms | 9428 KB | Output is correct |
28 | Correct | 105 ms | 10984 KB | Output is correct |
29 | Correct | 98 ms | 9424 KB | Output is correct |
30 | Correct | 100 ms | 10984 KB | Output is correct |
31 | Correct | 98 ms | 9356 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5752 KB | Output is correct |
2 | Correct | 7 ms | 5880 KB | Output is correct |
3 | Correct | 7 ms | 5880 KB | Output is correct |
4 | Correct | 6 ms | 5752 KB | Output is correct |
5 | Correct | 8 ms | 5940 KB | Output is correct |
6 | Correct | 8 ms | 5880 KB | Output is correct |
7 | Correct | 7 ms | 5752 KB | Output is correct |
8 | Correct | 7 ms | 5880 KB | Output is correct |
9 | Correct | 8 ms | 5880 KB | Output is correct |
10 | Correct | 8 ms | 5880 KB | Output is correct |
11 | Correct | 8 ms | 5880 KB | Output is correct |
12 | Correct | 8 ms | 5880 KB | Output is correct |
13 | Correct | 8 ms | 5880 KB | Output is correct |
14 | Correct | 8 ms | 5880 KB | Output is correct |
15 | Correct | 8 ms | 5880 KB | Output is correct |
16 | Correct | 212 ms | 15496 KB | Output is correct |
17 | Correct | 572 ms | 25836 KB | Output is correct |
18 | Correct | 42 ms | 7672 KB | Output is correct |
19 | Correct | 172 ms | 15656 KB | Output is correct |
20 | Correct | 592 ms | 25896 KB | Output is correct |
21 | Correct | 316 ms | 18800 KB | Output is correct |
22 | Correct | 186 ms | 14696 KB | Output is correct |
23 | Correct | 651 ms | 25888 KB | Output is correct |
24 | Correct | 596 ms | 25848 KB | Output is correct |
25 | Correct | 619 ms | 25920 KB | Output is correct |
26 | Correct | 168 ms | 15528 KB | Output is correct |
27 | Correct | 174 ms | 15548 KB | Output is correct |
28 | Correct | 172 ms | 15336 KB | Output is correct |
29 | Correct | 174 ms | 15468 KB | Output is correct |
30 | Correct | 175 ms | 15720 KB | Output is correct |
31 | Correct | 7 ms | 5728 KB | Output is correct |
32 | Correct | 6 ms | 5752 KB | Output is correct |
33 | Correct | 7 ms | 5880 KB | Output is correct |
34 | Correct | 7 ms | 5752 KB | Output is correct |
35 | Correct | 7 ms | 5752 KB | Output is correct |
36 | Correct | 7 ms | 5752 KB | Output is correct |
37 | Correct | 6 ms | 5752 KB | Output is correct |
38 | Correct | 6 ms | 5748 KB | Output is correct |
39 | Correct | 8 ms | 5752 KB | Output is correct |
40 | Correct | 7 ms | 5752 KB | Output is correct |
41 | Correct | 233 ms | 13268 KB | Output is correct |
42 | Correct | 489 ms | 21480 KB | Output is correct |
43 | Correct | 572 ms | 21432 KB | Output is correct |
44 | Correct | 106 ms | 9336 KB | Output is correct |
45 | Correct | 513 ms | 21360 KB | Output is correct |
46 | Correct | 504 ms | 21484 KB | Output is correct |
47 | Correct | 503 ms | 21392 KB | Output is correct |
48 | Correct | 496 ms | 21396 KB | Output is correct |
49 | Correct | 491 ms | 21408 KB | Output is correct |
50 | Correct | 493 ms | 21340 KB | Output is correct |
51 | Correct | 494 ms | 21304 KB | Output is correct |
52 | Correct | 519 ms | 21360 KB | Output is correct |
53 | Correct | 512 ms | 21268 KB | Output is correct |
54 | Correct | 568 ms | 21484 KB | Output is correct |
55 | Correct | 506 ms | 21736 KB | Output is correct |
56 | Correct | 493 ms | 21484 KB | Output is correct |
57 | Correct | 475 ms | 21336 KB | Output is correct |
58 | Correct | 480 ms | 21272 KB | Output is correct |
59 | Correct | 107 ms | 9336 KB | Output is correct |
60 | Correct | 519 ms | 21456 KB | Output is correct |
61 | Correct | 486 ms | 20976 KB | Output is correct |
62 | Correct | 104 ms | 10988 KB | Output is correct |
63 | Correct | 108 ms | 9912 KB | Output is correct |
64 | Correct | 112 ms | 11060 KB | Output is correct |
65 | Correct | 107 ms | 10988 KB | Output is correct |
66 | Correct | 112 ms | 10104 KB | Output is correct |
67 | Correct | 97 ms | 9428 KB | Output is correct |
68 | Correct | 105 ms | 10984 KB | Output is correct |
69 | Correct | 98 ms | 9424 KB | Output is correct |
70 | Correct | 100 ms | 10984 KB | Output is correct |
71 | Correct | 98 ms | 9356 KB | Output is correct |
72 | Correct | 302 ms | 18680 KB | Output is correct |
73 | Correct | 587 ms | 25992 KB | Output is correct |
74 | Correct | 567 ms | 26100 KB | Output is correct |
75 | Correct | 571 ms | 25996 KB | Output is correct |
76 | Correct | 573 ms | 26092 KB | Output is correct |
77 | Correct | 636 ms | 25808 KB | Output is correct |
78 | Correct | 620 ms | 25932 KB | Output is correct |
79 | Correct | 577 ms | 25992 KB | Output is correct |
80 | Correct | 580 ms | 25852 KB | Output is correct |
81 | Correct | 578 ms | 25836 KB | Output is correct |
82 | Correct | 591 ms | 25864 KB | Output is correct |
83 | Correct | 601 ms | 25960 KB | Output is correct |
84 | Correct | 618 ms | 25836 KB | Output is correct |
85 | Correct | 594 ms | 25956 KB | Output is correct |
86 | Correct | 571 ms | 25948 KB | Output is correct |
87 | Correct | 578 ms | 25860 KB | Output is correct |
88 | Correct | 565 ms | 25988 KB | Output is correct |
89 | Correct | 182 ms | 15136 KB | Output is correct |
90 | Correct | 572 ms | 25968 KB | Output is correct |
91 | Correct | 552 ms | 25544 KB | Output is correct |
92 | Correct | 184 ms | 16360 KB | Output is correct |
93 | Correct | 226 ms | 21228 KB | Output is correct |
94 | Correct | 180 ms | 16360 KB | Output is correct |
95 | Correct | 188 ms | 16312 KB | Output is correct |
96 | Correct | 246 ms | 21376 KB | Output is correct |
97 | Correct | 226 ms | 15284 KB | Output is correct |
98 | Correct | 176 ms | 16360 KB | Output is correct |
99 | Correct | 187 ms | 15248 KB | Output is correct |
100 | Correct | 182 ms | 16416 KB | Output is correct |