# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
202265 | 2020-02-14T19:55:15 Z | ZwariowanyMarcin | Evacuation plan (IZhO18_plan) | C++14 | 1355 ms | 33540 KB |
#include <bits/stdc++.h> #define LL long long #define pb push_back #define mp make_pair #define ss(x) (int) x.size() #define fi first #define se second #define cat(x) cerr << #x << " = " << x << endl using namespace std; const int nax = 1e5 + 111; const int INF = 1e9 + 111; int n, m; int a, b, c; vector <pair<int, int>> v[nax]; int k; vector <int> special; int q; int d[nax]; int e[nax]; int L[nax]; int R[nax]; int M[nax]; int G[nax]; int dis[nax]; bool odw[nax]; priority_queue <pair<int, int>> kol; struct uf { int p[nax]; void init() { for (int i = 1; i <= n; ++i) p[i] = i; } int find(int x) { if (x == p[x]) return x; return p[x] = find(p[x]); } void unia(int x, int y) { x = find(x); y = find(y); p[x] = y; } } ja; vector <pair<int, int>> vec; vector <pair<int, int>> id; bool akt[nax]; void solve() { ja.init(); sort(id.begin(), id.end()); for (int i = 1; i <= n; ++i) akt[i] = 0; int j = ss(vec) - 1; for (int i = ss(id) - 1; 0 <= i; --i) { while (0 <= j && id[i].fi <= vec[j].fi) { int u = vec[j].se; akt[u] = 1; for (auto it : v[u]) if (akt[it.fi]) ja.unia(u, it.fi); j--; } int ID = id[i].se; G[ID] = (ja.find(d[ID]) == ja.find(e[ID])); } } int main() { scanf ("%d%d", &n, &m); for (int i = 1; i <= m; ++i) { scanf ("%d%d%d", &a, &b, &c); v[a].pb(mp(b, c)); v[b].pb(mp(a, c)); } scanf ("%d", &k); while (k--) { scanf ("%d", &a); special.pb(a); } scanf ("%d", &q); for (int i = 1; i <= q; ++i) { scanf ("%d%d", d + i, e + i); L[i] = 0; R[i] = INF; } for (int i = 1; i <= n; ++i) dis[i] = INF; for (auto it : special) { dis[it] = 0; kol.push({0, it}); } while (!kol.empty()) { int ja = kol.top().se; kol.pop(); if (odw[ja]) continue; odw[ja] = 1; for (auto it : v[ja]) { int d = dis[ja] + it.se; if (d < dis[it.fi]) { dis[it.fi] = d; kol.push({-d, it.fi}); } } } for (int i = 1; i <= n; ++i) vec.pb({dis[i], i}); sort(vec.begin(), vec.end()); for (int i = 1; i <= 32; ++i) { id.clear(); for (int j = 1; j <= q; ++j) { M[j] = (L[j] + R[j] + 1) / 2; id.pb({M[j], j}); } solve(); for (int j = 1; j <= q; ++j) { if (G[j] == 0) R[j] = M[j] - 1; else L[j] = M[j]; } } for (int i = 1; i <= q; ++i) printf ("%d\n", L[i]); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2684 KB | Output is correct |
2 | Correct | 9 ms | 2808 KB | Output is correct |
3 | Correct | 9 ms | 2808 KB | Output is correct |
4 | Correct | 6 ms | 2680 KB | Output is correct |
5 | Correct | 9 ms | 2808 KB | Output is correct |
6 | Correct | 9 ms | 2808 KB | Output is correct |
7 | Correct | 7 ms | 2680 KB | Output is correct |
8 | Correct | 6 ms | 2680 KB | Output is correct |
9 | Correct | 10 ms | 2808 KB | Output is correct |
10 | Correct | 9 ms | 2808 KB | Output is correct |
11 | Correct | 10 ms | 2812 KB | Output is correct |
12 | Correct | 9 ms | 2808 KB | Output is correct |
13 | Correct | 10 ms | 2808 KB | Output is correct |
14 | Correct | 10 ms | 2808 KB | Output is correct |
15 | Correct | 10 ms | 2936 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2684 KB | Output is correct |
2 | Correct | 9 ms | 2808 KB | Output is correct |
3 | Correct | 9 ms | 2808 KB | Output is correct |
4 | Correct | 6 ms | 2680 KB | Output is correct |
5 | Correct | 9 ms | 2808 KB | Output is correct |
6 | Correct | 9 ms | 2808 KB | Output is correct |
7 | Correct | 7 ms | 2680 KB | Output is correct |
8 | Correct | 6 ms | 2680 KB | Output is correct |
9 | Correct | 10 ms | 2808 KB | Output is correct |
10 | Correct | 9 ms | 2808 KB | Output is correct |
11 | Correct | 10 ms | 2812 KB | Output is correct |
12 | Correct | 9 ms | 2808 KB | Output is correct |
13 | Correct | 10 ms | 2808 KB | Output is correct |
14 | Correct | 10 ms | 2808 KB | Output is correct |
15 | Correct | 10 ms | 2936 KB | Output is correct |
16 | Correct | 654 ms | 14472 KB | Output is correct |
17 | Correct | 1302 ms | 32544 KB | Output is correct |
18 | Correct | 81 ms | 5496 KB | Output is correct |
19 | Correct | 333 ms | 16476 KB | Output is correct |
20 | Correct | 1268 ms | 32492 KB | Output is correct |
21 | Correct | 591 ms | 19948 KB | Output is correct |
22 | Correct | 698 ms | 14700 KB | Output is correct |
23 | Correct | 1254 ms | 32492 KB | Output is correct |
24 | Correct | 1242 ms | 32616 KB | Output is correct |
25 | Correct | 1101 ms | 32612 KB | Output is correct |
26 | Correct | 346 ms | 16748 KB | Output is correct |
27 | Correct | 350 ms | 17132 KB | Output is correct |
28 | Correct | 351 ms | 16620 KB | Output is correct |
29 | Correct | 342 ms | 16620 KB | Output is correct |
30 | Correct | 343 ms | 16252 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2680 KB | Output is correct |
2 | Correct | 6 ms | 2728 KB | Output is correct |
3 | Correct | 6 ms | 2684 KB | Output is correct |
4 | Correct | 6 ms | 2680 KB | Output is correct |
5 | Correct | 6 ms | 2680 KB | Output is correct |
6 | Correct | 6 ms | 2680 KB | Output is correct |
7 | Correct | 7 ms | 2684 KB | Output is correct |
8 | Correct | 6 ms | 2680 KB | Output is correct |
9 | Correct | 6 ms | 2680 KB | Output is correct |
10 | Correct | 7 ms | 2680 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 337 ms | 14700 KB | Output is correct |
2 | Correct | 659 ms | 27884 KB | Output is correct |
3 | Correct | 698 ms | 27808 KB | Output is correct |
4 | Correct | 185 ms | 9584 KB | Output is correct |
5 | Correct | 851 ms | 27856 KB | Output is correct |
6 | Correct | 597 ms | 28012 KB | Output is correct |
7 | Correct | 625 ms | 27884 KB | Output is correct |
8 | Correct | 555 ms | 27880 KB | Output is correct |
9 | Correct | 606 ms | 27904 KB | Output is correct |
10 | Correct | 795 ms | 28012 KB | Output is correct |
11 | Correct | 850 ms | 28008 KB | Output is correct |
12 | Correct | 757 ms | 27884 KB | Output is correct |
13 | Correct | 831 ms | 27880 KB | Output is correct |
14 | Correct | 609 ms | 28140 KB | Output is correct |
15 | Correct | 783 ms | 28772 KB | Output is correct |
16 | Correct | 780 ms | 28012 KB | Output is correct |
17 | Correct | 614 ms | 27880 KB | Output is correct |
18 | Correct | 623 ms | 27924 KB | Output is correct |
19 | Correct | 85 ms | 9328 KB | Output is correct |
20 | Correct | 807 ms | 27884 KB | Output is correct |
21 | Correct | 563 ms | 28524 KB | Output is correct |
22 | Correct | 150 ms | 12524 KB | Output is correct |
23 | Correct | 221 ms | 9856 KB | Output is correct |
24 | Correct | 123 ms | 11624 KB | Output is correct |
25 | Correct | 159 ms | 12264 KB | Output is correct |
26 | Correct | 228 ms | 9964 KB | Output is correct |
27 | Correct | 184 ms | 9328 KB | Output is correct |
28 | Correct | 139 ms | 11640 KB | Output is correct |
29 | Correct | 196 ms | 9328 KB | Output is correct |
30 | Correct | 133 ms | 11752 KB | Output is correct |
31 | Correct | 200 ms | 9324 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2684 KB | Output is correct |
2 | Correct | 9 ms | 2808 KB | Output is correct |
3 | Correct | 9 ms | 2808 KB | Output is correct |
4 | Correct | 6 ms | 2680 KB | Output is correct |
5 | Correct | 9 ms | 2808 KB | Output is correct |
6 | Correct | 9 ms | 2808 KB | Output is correct |
7 | Correct | 7 ms | 2680 KB | Output is correct |
8 | Correct | 6 ms | 2680 KB | Output is correct |
9 | Correct | 10 ms | 2808 KB | Output is correct |
10 | Correct | 9 ms | 2808 KB | Output is correct |
11 | Correct | 10 ms | 2812 KB | Output is correct |
12 | Correct | 9 ms | 2808 KB | Output is correct |
13 | Correct | 10 ms | 2808 KB | Output is correct |
14 | Correct | 10 ms | 2808 KB | Output is correct |
15 | Correct | 10 ms | 2936 KB | Output is correct |
16 | Correct | 654 ms | 14472 KB | Output is correct |
17 | Correct | 1302 ms | 32544 KB | Output is correct |
18 | Correct | 81 ms | 5496 KB | Output is correct |
19 | Correct | 333 ms | 16476 KB | Output is correct |
20 | Correct | 1268 ms | 32492 KB | Output is correct |
21 | Correct | 591 ms | 19948 KB | Output is correct |
22 | Correct | 698 ms | 14700 KB | Output is correct |
23 | Correct | 1254 ms | 32492 KB | Output is correct |
24 | Correct | 1242 ms | 32616 KB | Output is correct |
25 | Correct | 1101 ms | 32612 KB | Output is correct |
26 | Correct | 346 ms | 16748 KB | Output is correct |
27 | Correct | 350 ms | 17132 KB | Output is correct |
28 | Correct | 351 ms | 16620 KB | Output is correct |
29 | Correct | 342 ms | 16620 KB | Output is correct |
30 | Correct | 343 ms | 16252 KB | Output is correct |
31 | Correct | 6 ms | 2680 KB | Output is correct |
32 | Correct | 6 ms | 2728 KB | Output is correct |
33 | Correct | 6 ms | 2684 KB | Output is correct |
34 | Correct | 6 ms | 2680 KB | Output is correct |
35 | Correct | 6 ms | 2680 KB | Output is correct |
36 | Correct | 6 ms | 2680 KB | Output is correct |
37 | Correct | 7 ms | 2684 KB | Output is correct |
38 | Correct | 6 ms | 2680 KB | Output is correct |
39 | Correct | 6 ms | 2680 KB | Output is correct |
40 | Correct | 7 ms | 2680 KB | Output is correct |
41 | Correct | 337 ms | 14700 KB | Output is correct |
42 | Correct | 659 ms | 27884 KB | Output is correct |
43 | Correct | 698 ms | 27808 KB | Output is correct |
44 | Correct | 185 ms | 9584 KB | Output is correct |
45 | Correct | 851 ms | 27856 KB | Output is correct |
46 | Correct | 597 ms | 28012 KB | Output is correct |
47 | Correct | 625 ms | 27884 KB | Output is correct |
48 | Correct | 555 ms | 27880 KB | Output is correct |
49 | Correct | 606 ms | 27904 KB | Output is correct |
50 | Correct | 795 ms | 28012 KB | Output is correct |
51 | Correct | 850 ms | 28008 KB | Output is correct |
52 | Correct | 757 ms | 27884 KB | Output is correct |
53 | Correct | 831 ms | 27880 KB | Output is correct |
54 | Correct | 609 ms | 28140 KB | Output is correct |
55 | Correct | 783 ms | 28772 KB | Output is correct |
56 | Correct | 780 ms | 28012 KB | Output is correct |
57 | Correct | 614 ms | 27880 KB | Output is correct |
58 | Correct | 623 ms | 27924 KB | Output is correct |
59 | Correct | 85 ms | 9328 KB | Output is correct |
60 | Correct | 807 ms | 27884 KB | Output is correct |
61 | Correct | 563 ms | 28524 KB | Output is correct |
62 | Correct | 150 ms | 12524 KB | Output is correct |
63 | Correct | 221 ms | 9856 KB | Output is correct |
64 | Correct | 123 ms | 11624 KB | Output is correct |
65 | Correct | 159 ms | 12264 KB | Output is correct |
66 | Correct | 228 ms | 9964 KB | Output is correct |
67 | Correct | 184 ms | 9328 KB | Output is correct |
68 | Correct | 139 ms | 11640 KB | Output is correct |
69 | Correct | 196 ms | 9328 KB | Output is correct |
70 | Correct | 133 ms | 11752 KB | Output is correct |
71 | Correct | 200 ms | 9324 KB | Output is correct |
72 | Correct | 951 ms | 19700 KB | Output is correct |
73 | Correct | 1324 ms | 32616 KB | Output is correct |
74 | Correct | 1355 ms | 32620 KB | Output is correct |
75 | Correct | 1266 ms | 32620 KB | Output is correct |
76 | Correct | 1303 ms | 32732 KB | Output is correct |
77 | Correct | 1299 ms | 32624 KB | Output is correct |
78 | Correct | 1314 ms | 32740 KB | Output is correct |
79 | Correct | 1257 ms | 32492 KB | Output is correct |
80 | Correct | 1340 ms | 32668 KB | Output is correct |
81 | Correct | 1320 ms | 32664 KB | Output is correct |
82 | Correct | 1289 ms | 32740 KB | Output is correct |
83 | Correct | 1278 ms | 32656 KB | Output is correct |
84 | Correct | 1243 ms | 32748 KB | Output is correct |
85 | Correct | 1159 ms | 33540 KB | Output is correct |
86 | Correct | 1258 ms | 32640 KB | Output is correct |
87 | Correct | 1229 ms | 32632 KB | Output is correct |
88 | Correct | 1293 ms | 32496 KB | Output is correct |
89 | Correct | 704 ms | 14700 KB | Output is correct |
90 | Correct | 1274 ms | 32528 KB | Output is correct |
91 | Correct | 794 ms | 32876 KB | Output is correct |
92 | Correct | 349 ms | 16440 KB | Output is correct |
93 | Correct | 731 ms | 14988 KB | Output is correct |
94 | Correct | 342 ms | 17012 KB | Output is correct |
95 | Correct | 354 ms | 17260 KB | Output is correct |
96 | Correct | 627 ms | 14620 KB | Output is correct |
97 | Correct | 650 ms | 14196 KB | Output is correct |
98 | Correct | 358 ms | 15992 KB | Output is correct |
99 | Correct | 675 ms | 14316 KB | Output is correct |
100 | Correct | 362 ms | 16460 KB | Output is correct |