# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
65177 | 2018-08-07T00:12:05 Z | kingpig9 | Evacuation plan (IZhO18_plan) | C++11 | 1483 ms | 20992 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int MAXN = 1e5 + 10, INF = 1e8; #define debug(...) fprintf(stderr, __VA_ARGS__) #define all(v) (v).begin(), (v).end() #define fi first #define se second #define fillchar(a, s) memset((a), (s), sizeof(a)) int N, M; vector<pii> adj[MAXN]; struct union_find { int par[MAXN]; void reset() { for (int i = 0; i < N; i++) { par[i] = i; } } int find (int x) { return x == par[x] ? x : par[x] = find(par[x]); } void merge (int x, int y) { par[find(x)] = find(y); } } uf; int K, G[MAXN]; int dist[MAXN]; bool vis[MAXN]; int dord[MAXN]; //order of dist int Q; int S[MAXN], T[MAXN]; int ind[MAXN], lo[MAXN], hi[MAXN], mid[MAXN]; //code for dijkstra void dijkstra() { priority_queue<pii, vector<pii>, greater<pii>> pq; for (int i = 0; i < N; i++) { dist[i] = INF; } for (int i = 0; i < K; i++) { int x = G[i]; dist[x] = 0; pq.push({0, x}); } while (!pq.empty()) { int u = pq.top().se, w = pq.top().fi; pq.pop(); if (vis[u]) { continue; } vis[u] = true; for (pii e : adj[u]) { int v = e.se; int nw = e.fi + w; if (dist[v] > nw) { dist[v] = nw; pq.push({nw, v}); } } } /* for (int i = 0; i < N; i++) { debug("dist[%d] = %d\n", i, dist[i]); } */ } bool cmpd (int x, int y) { return dist[x] > dist[y]; } bool cmp (int x, int y) { return mid[x] > mid[y]; } int main() { scanf("%d %d", &N, &M); for (int i = 0; i < M; i++) { int a, b, w; scanf("%d %d %d", &a, &b, &w); a--; b--; adj[a].push_back({w, b}); adj[b].push_back({w, a}); } scanf("%d", &K); for (int i = 0; i < K; i++) { scanf("%d", &G[i]); G[i]--; } dijkstra(); scanf("%d", &Q); for (int i = 0; i < Q; i++) { scanf("%d %d", &S[i], &T[i]); S[i]--; T[i]--; lo[i] = 0; //ans always >= lo[i], always < hi[i] hi[i] = INF; } iota(dord, dord + N, 0); sort(dord, dord + N, cmpd); //code for parallel bsearch for (int iter = 0; iter < 28; iter++) { for (int i = 0; i < Q; i++) { mid[i] = (lo[i] + hi[i]) / 2; ind[i] = i; } sort(ind, ind + Q, cmp); uf.reset(); int dptr = 0; for (int ii = 0; ii < Q; ii++) { int i = ind[ii]; for (; dptr < N && dist[dord[dptr]] >= mid[i]; dptr++) { //try to merge if you can int x = dord[dptr]; for (pii e : adj[x]) { int y = e.se; if (dist[y] >= mid[i]) { uf.merge(x, y); } } } if (uf.find(S[i]) == uf.find(T[i])) { lo[i] = mid[i]; } else { hi[i] = mid[i]; } } } //code for final output for (int i = 0; i < Q; i++) { printf("%d\n", lo[i]); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2652 KB | Output is correct |
2 | Correct | 6 ms | 2808 KB | Output is correct |
3 | Correct | 6 ms | 2808 KB | Output is correct |
4 | Correct | 4 ms | 2680 KB | Output is correct |
5 | Correct | 6 ms | 2780 KB | Output is correct |
6 | Correct | 6 ms | 2780 KB | Output is correct |
7 | Correct | 4 ms | 2680 KB | Output is correct |
8 | Correct | 4 ms | 2780 KB | Output is correct |
9 | Correct | 7 ms | 2808 KB | Output is correct |
10 | Correct | 6 ms | 2808 KB | Output is correct |
11 | Correct | 7 ms | 2808 KB | Output is correct |
12 | Correct | 6 ms | 2808 KB | Output is correct |
13 | Correct | 7 ms | 2808 KB | Output is correct |
14 | Correct | 7 ms | 2808 KB | Output is correct |
15 | Correct | 7 ms | 2808 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2652 KB | Output is correct |
2 | Correct | 6 ms | 2808 KB | Output is correct |
3 | Correct | 6 ms | 2808 KB | Output is correct |
4 | Correct | 4 ms | 2680 KB | Output is correct |
5 | Correct | 6 ms | 2780 KB | Output is correct |
6 | Correct | 6 ms | 2780 KB | Output is correct |
7 | Correct | 4 ms | 2680 KB | Output is correct |
8 | Correct | 4 ms | 2780 KB | Output is correct |
9 | Correct | 7 ms | 2808 KB | Output is correct |
10 | Correct | 6 ms | 2808 KB | Output is correct |
11 | Correct | 7 ms | 2808 KB | Output is correct |
12 | Correct | 6 ms | 2808 KB | Output is correct |
13 | Correct | 7 ms | 2808 KB | Output is correct |
14 | Correct | 7 ms | 2808 KB | Output is correct |
15 | Correct | 7 ms | 2808 KB | Output is correct |
16 | Correct | 608 ms | 10296 KB | Output is correct |
17 | Correct | 1403 ms | 20884 KB | Output is correct |
18 | Correct | 80 ms | 4516 KB | Output is correct |
19 | Correct | 312 ms | 12272 KB | Output is correct |
20 | Correct | 1395 ms | 20872 KB | Output is correct |
21 | Correct | 522 ms | 13304 KB | Output is correct |
22 | Correct | 834 ms | 10848 KB | Output is correct |
23 | Correct | 1405 ms | 20860 KB | Output is correct |
24 | Correct | 1361 ms | 20880 KB | Output is correct |
25 | Correct | 1196 ms | 20784 KB | Output is correct |
26 | Correct | 310 ms | 10616 KB | Output is correct |
27 | Correct | 310 ms | 10656 KB | Output is correct |
28 | Correct | 306 ms | 11412 KB | Output is correct |
29 | Correct | 304 ms | 10680 KB | Output is correct |
30 | Correct | 331 ms | 10900 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 4 ms | 2680 KB | Output is correct |
3 | Correct | 4 ms | 2680 KB | Output is correct |
4 | Correct | 4 ms | 2680 KB | Output is correct |
5 | Correct | 4 ms | 2684 KB | Output is correct |
6 | Correct | 4 ms | 2680 KB | Output is correct |
7 | Correct | 4 ms | 2680 KB | Output is correct |
8 | Correct | 4 ms | 2680 KB | Output is correct |
9 | Correct | 4 ms | 2680 KB | Output is correct |
10 | Correct | 4 ms | 2680 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 461 ms | 10684 KB | Output is correct |
2 | Correct | 940 ms | 18356 KB | Output is correct |
3 | Correct | 967 ms | 18376 KB | Output is correct |
4 | Correct | 450 ms | 8108 KB | Output is correct |
5 | Correct | 1244 ms | 18364 KB | Output is correct |
6 | Correct | 645 ms | 18440 KB | Output is correct |
7 | Correct | 838 ms | 18504 KB | Output is correct |
8 | Correct | 596 ms | 18456 KB | Output is correct |
9 | Correct | 693 ms | 18428 KB | Output is correct |
10 | Correct | 1034 ms | 18480 KB | Output is correct |
11 | Correct | 1235 ms | 18444 KB | Output is correct |
12 | Correct | 997 ms | 18404 KB | Output is correct |
13 | Correct | 1091 ms | 19148 KB | Output is correct |
14 | Correct | 735 ms | 19208 KB | Output is correct |
15 | Correct | 989 ms | 20204 KB | Output is correct |
16 | Correct | 962 ms | 19192 KB | Output is correct |
17 | Correct | 730 ms | 19168 KB | Output is correct |
18 | Correct | 696 ms | 19112 KB | Output is correct |
19 | Correct | 102 ms | 8184 KB | Output is correct |
20 | Correct | 868 ms | 19152 KB | Output is correct |
21 | Correct | 560 ms | 19164 KB | Output is correct |
22 | Correct | 115 ms | 8552 KB | Output is correct |
23 | Correct | 224 ms | 7612 KB | Output is correct |
24 | Correct | 118 ms | 8560 KB | Output is correct |
25 | Correct | 113 ms | 8556 KB | Output is correct |
26 | Correct | 204 ms | 7716 KB | Output is correct |
27 | Correct | 410 ms | 8040 KB | Output is correct |
28 | Correct | 113 ms | 8556 KB | Output is correct |
29 | Correct | 411 ms | 7844 KB | Output is correct |
30 | Correct | 111 ms | 8652 KB | Output is correct |
31 | Correct | 318 ms | 7940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2652 KB | Output is correct |
2 | Correct | 6 ms | 2808 KB | Output is correct |
3 | Correct | 6 ms | 2808 KB | Output is correct |
4 | Correct | 4 ms | 2680 KB | Output is correct |
5 | Correct | 6 ms | 2780 KB | Output is correct |
6 | Correct | 6 ms | 2780 KB | Output is correct |
7 | Correct | 4 ms | 2680 KB | Output is correct |
8 | Correct | 4 ms | 2780 KB | Output is correct |
9 | Correct | 7 ms | 2808 KB | Output is correct |
10 | Correct | 6 ms | 2808 KB | Output is correct |
11 | Correct | 7 ms | 2808 KB | Output is correct |
12 | Correct | 6 ms | 2808 KB | Output is correct |
13 | Correct | 7 ms | 2808 KB | Output is correct |
14 | Correct | 7 ms | 2808 KB | Output is correct |
15 | Correct | 7 ms | 2808 KB | Output is correct |
16 | Correct | 608 ms | 10296 KB | Output is correct |
17 | Correct | 1403 ms | 20884 KB | Output is correct |
18 | Correct | 80 ms | 4516 KB | Output is correct |
19 | Correct | 312 ms | 12272 KB | Output is correct |
20 | Correct | 1395 ms | 20872 KB | Output is correct |
21 | Correct | 522 ms | 13304 KB | Output is correct |
22 | Correct | 834 ms | 10848 KB | Output is correct |
23 | Correct | 1405 ms | 20860 KB | Output is correct |
24 | Correct | 1361 ms | 20880 KB | Output is correct |
25 | Correct | 1196 ms | 20784 KB | Output is correct |
26 | Correct | 310 ms | 10616 KB | Output is correct |
27 | Correct | 310 ms | 10656 KB | Output is correct |
28 | Correct | 306 ms | 11412 KB | Output is correct |
29 | Correct | 304 ms | 10680 KB | Output is correct |
30 | Correct | 331 ms | 10900 KB | Output is correct |
31 | Correct | 4 ms | 2680 KB | Output is correct |
32 | Correct | 4 ms | 2680 KB | Output is correct |
33 | Correct | 4 ms | 2680 KB | Output is correct |
34 | Correct | 4 ms | 2680 KB | Output is correct |
35 | Correct | 4 ms | 2684 KB | Output is correct |
36 | Correct | 4 ms | 2680 KB | Output is correct |
37 | Correct | 4 ms | 2680 KB | Output is correct |
38 | Correct | 4 ms | 2680 KB | Output is correct |
39 | Correct | 4 ms | 2680 KB | Output is correct |
40 | Correct | 4 ms | 2680 KB | Output is correct |
41 | Correct | 461 ms | 10684 KB | Output is correct |
42 | Correct | 940 ms | 18356 KB | Output is correct |
43 | Correct | 967 ms | 18376 KB | Output is correct |
44 | Correct | 450 ms | 8108 KB | Output is correct |
45 | Correct | 1244 ms | 18364 KB | Output is correct |
46 | Correct | 645 ms | 18440 KB | Output is correct |
47 | Correct | 838 ms | 18504 KB | Output is correct |
48 | Correct | 596 ms | 18456 KB | Output is correct |
49 | Correct | 693 ms | 18428 KB | Output is correct |
50 | Correct | 1034 ms | 18480 KB | Output is correct |
51 | Correct | 1235 ms | 18444 KB | Output is correct |
52 | Correct | 997 ms | 18404 KB | Output is correct |
53 | Correct | 1091 ms | 19148 KB | Output is correct |
54 | Correct | 735 ms | 19208 KB | Output is correct |
55 | Correct | 989 ms | 20204 KB | Output is correct |
56 | Correct | 962 ms | 19192 KB | Output is correct |
57 | Correct | 730 ms | 19168 KB | Output is correct |
58 | Correct | 696 ms | 19112 KB | Output is correct |
59 | Correct | 102 ms | 8184 KB | Output is correct |
60 | Correct | 868 ms | 19152 KB | Output is correct |
61 | Correct | 560 ms | 19164 KB | Output is correct |
62 | Correct | 115 ms | 8552 KB | Output is correct |
63 | Correct | 224 ms | 7612 KB | Output is correct |
64 | Correct | 118 ms | 8560 KB | Output is correct |
65 | Correct | 113 ms | 8556 KB | Output is correct |
66 | Correct | 204 ms | 7716 KB | Output is correct |
67 | Correct | 410 ms | 8040 KB | Output is correct |
68 | Correct | 113 ms | 8556 KB | Output is correct |
69 | Correct | 411 ms | 7844 KB | Output is correct |
70 | Correct | 111 ms | 8652 KB | Output is correct |
71 | Correct | 318 ms | 7940 KB | Output is correct |
72 | Correct | 914 ms | 13628 KB | Output is correct |
73 | Correct | 1483 ms | 20868 KB | Output is correct |
74 | Correct | 1401 ms | 20840 KB | Output is correct |
75 | Correct | 1413 ms | 20904 KB | Output is correct |
76 | Correct | 1388 ms | 20892 KB | Output is correct |
77 | Correct | 1370 ms | 20900 KB | Output is correct |
78 | Correct | 1408 ms | 20884 KB | Output is correct |
79 | Correct | 1432 ms | 20836 KB | Output is correct |
80 | Correct | 1364 ms | 20896 KB | Output is correct |
81 | Correct | 1403 ms | 20844 KB | Output is correct |
82 | Correct | 1343 ms | 20864 KB | Output is correct |
83 | Correct | 1289 ms | 20896 KB | Output is correct |
84 | Correct | 1224 ms | 20860 KB | Output is correct |
85 | Correct | 1252 ms | 20784 KB | Output is correct |
86 | Correct | 1416 ms | 20896 KB | Output is correct |
87 | Correct | 1326 ms | 20848 KB | Output is correct |
88 | Correct | 1446 ms | 20992 KB | Output is correct |
89 | Correct | 1114 ms | 11048 KB | Output is correct |
90 | Correct | 1385 ms | 20856 KB | Output is correct |
91 | Correct | 763 ms | 20960 KB | Output is correct |
92 | Correct | 330 ms | 11672 KB | Output is correct |
93 | Correct | 725 ms | 10664 KB | Output is correct |
94 | Correct | 304 ms | 10616 KB | Output is correct |
95 | Correct | 328 ms | 11352 KB | Output is correct |
96 | Correct | 532 ms | 10276 KB | Output is correct |
97 | Correct | 991 ms | 10380 KB | Output is correct |
98 | Correct | 319 ms | 11760 KB | Output is correct |
99 | Correct | 986 ms | 10384 KB | Output is correct |
100 | Correct | 324 ms | 11976 KB | Output is correct |