# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
40495 | 2018-02-03T05:16:26 Z | Just_Solve_The_Problem | Evacuation plan (IZhO18_plan) | C++11 | 937 ms | 40864 KB |
#include <bits/stdc++.h> using namespace std; #define pii pair < int, int > #define pb push_back #define mk make_pair #define fr first #define sc second #define ok puts("ok"); const int N = (int)2e5 + 7; const int inf = (int)1e9 + 7; vector < pii > gr[N]; vector < int > newgr[N]; int dist[N]; int p[N], pr[N], par[N]; set < pii > s; bool was[N]; int up[22][N]; int tin[N], tout[N]; int tiktak; void fun () { while (!s.empty()) { pii v = *s.begin(); s.erase(s.begin()); for (auto to : gr[v.sc]) { if (dist[to.fr] > dist[v.sc] + to.sc) { s.erase(mk(dist[to.fr], to.fr)); dist[to.fr] = dist[v.sc] + to.sc; s.insert(mk(dist[to.fr], to.fr)); } } } } int get_par (int v) { if (pr[v] == v) return v; return pr[v] = get_par(pr[v]); } void connect (int a, int b) { a = get_par(a); b = get_par(b); if (a != b) { pr[a] = b; } } bool upper (int a, int b) { return tin[a] <= tin[b] && tout[a] >= tout[b]; } void dfs (int v) { tin[v] = ++tiktak; up[0][v] = par[v]; for (int i = 1; i <= 20; i++) { up[i][v] = up[i - 1][up[i - 1][v]]; } for (int to : newgr[v]) { if (to != par[v]) { dfs(to); } } tout[v] = ++tiktak; } int get (int a, int b) { if (upper(a, b)) return a; if (upper(b, a)) return b; for (int i = 20; i >= 0; i--) { if (!upper(up[i][a], b)) a = up[i][a]; } return up[0][a]; } main () { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { pr[i] = i; dist[i] = inf; } for (int i = 1; i <= m; i++) { int a, b, c; scanf ("%d %d %d", &a, &b, &c); gr[a].pb(mk(b, c)); gr[b].pb(mk(a, c)); } int k; scanf ("%d", &k); for (int i = 1; i <= k; i++) { int a; scanf ("%d", &a); dist[a] = 0; s.insert(mk(0, a)); } fun(); vector < pii > vec; for (int i = 1; i <= n; i++) { vec.pb(mk(dist[i], i)); } sort(vec.begin(), vec.end(), greater < pii > ()); for (int i = 0; i < n; i++) { int a = vec[i].sc; was[a] = 1; for (auto to : gr[a]) { int b = to.fr; if (was[b]) { b = get_par(b); if (a != b) { connect(b, a); par[b] = a; newgr[b].pb(a); newgr[a].pb(b); } } } } par[vec[n - 1].sc] = vec[n - 1].sc; dfs(vec[n - 1].sc); int q; scanf ("%d", &q); while (q--) { int a, b; scanf ("%d %d", &a, &b); int qwe = get(a, b); printf ("%d\n", dist[qwe]); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9848 KB | Output is correct |
2 | Correct | 11 ms | 10072 KB | Output is correct |
3 | Correct | 11 ms | 9976 KB | Output is correct |
4 | Correct | 10 ms | 9820 KB | Output is correct |
5 | Correct | 11 ms | 9976 KB | Output is correct |
6 | Correct | 11 ms | 10104 KB | Output is correct |
7 | Correct | 10 ms | 9848 KB | Output is correct |
8 | Correct | 10 ms | 9820 KB | Output is correct |
9 | Correct | 11 ms | 10104 KB | Output is correct |
10 | Correct | 11 ms | 10108 KB | Output is correct |
11 | Correct | 11 ms | 10056 KB | Output is correct |
12 | Correct | 11 ms | 9976 KB | Output is correct |
13 | Correct | 11 ms | 10012 KB | Output is correct |
14 | Correct | 11 ms | 10076 KB | Output is correct |
15 | Correct | 12 ms | 10088 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9848 KB | Output is correct |
2 | Correct | 11 ms | 10072 KB | Output is correct |
3 | Correct | 11 ms | 9976 KB | Output is correct |
4 | Correct | 10 ms | 9820 KB | Output is correct |
5 | Correct | 11 ms | 9976 KB | Output is correct |
6 | Correct | 11 ms | 10104 KB | Output is correct |
7 | Correct | 10 ms | 9848 KB | Output is correct |
8 | Correct | 10 ms | 9820 KB | Output is correct |
9 | Correct | 11 ms | 10104 KB | Output is correct |
10 | Correct | 11 ms | 10108 KB | Output is correct |
11 | Correct | 11 ms | 10056 KB | Output is correct |
12 | Correct | 11 ms | 9976 KB | Output is correct |
13 | Correct | 11 ms | 10012 KB | Output is correct |
14 | Correct | 11 ms | 10076 KB | Output is correct |
15 | Correct | 12 ms | 10088 KB | Output is correct |
16 | Correct | 247 ms | 25572 KB | Output is correct |
17 | Correct | 786 ms | 39720 KB | Output is correct |
18 | Correct | 56 ms | 13084 KB | Output is correct |
19 | Correct | 232 ms | 28804 KB | Output is correct |
20 | Correct | 772 ms | 39780 KB | Output is correct |
21 | Correct | 419 ms | 31912 KB | Output is correct |
22 | Correct | 245 ms | 31160 KB | Output is correct |
23 | Correct | 937 ms | 39644 KB | Output is correct |
24 | Correct | 783 ms | 39704 KB | Output is correct |
25 | Correct | 798 ms | 39600 KB | Output is correct |
26 | Correct | 228 ms | 28576 KB | Output is correct |
27 | Correct | 232 ms | 28608 KB | Output is correct |
28 | Correct | 224 ms | 28576 KB | Output is correct |
29 | Correct | 226 ms | 28632 KB | Output is correct |
30 | Correct | 230 ms | 28824 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9848 KB | Output is correct |
2 | Correct | 10 ms | 9848 KB | Output is correct |
3 | Correct | 10 ms | 9976 KB | Output is correct |
4 | Correct | 10 ms | 9848 KB | Output is correct |
5 | Correct | 10 ms | 9848 KB | Output is correct |
6 | Correct | 10 ms | 9848 KB | Output is correct |
7 | Correct | 10 ms | 9848 KB | Output is correct |
8 | Correct | 10 ms | 9848 KB | Output is correct |
9 | Correct | 10 ms | 9848 KB | Output is correct |
10 | Correct | 10 ms | 9848 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 395 ms | 31648 KB | Output is correct |
2 | Correct | 771 ms | 39196 KB | Output is correct |
3 | Correct | 762 ms | 39224 KB | Output is correct |
4 | Correct | 185 ms | 28656 KB | Output is correct |
5 | Correct | 767 ms | 39308 KB | Output is correct |
6 | Correct | 800 ms | 39276 KB | Output is correct |
7 | Correct | 792 ms | 39228 KB | Output is correct |
8 | Correct | 769 ms | 39256 KB | Output is correct |
9 | Correct | 787 ms | 39284 KB | Output is correct |
10 | Correct | 791 ms | 39296 KB | Output is correct |
11 | Correct | 739 ms | 39216 KB | Output is correct |
12 | Correct | 751 ms | 39288 KB | Output is correct |
13 | Correct | 734 ms | 39420 KB | Output is correct |
14 | Correct | 786 ms | 39244 KB | Output is correct |
15 | Correct | 790 ms | 39296 KB | Output is correct |
16 | Correct | 780 ms | 39304 KB | Output is correct |
17 | Correct | 785 ms | 39180 KB | Output is correct |
18 | Correct | 763 ms | 39244 KB | Output is correct |
19 | Correct | 194 ms | 30236 KB | Output is correct |
20 | Correct | 735 ms | 39296 KB | Output is correct |
21 | Correct | 633 ms | 39288 KB | Output is correct |
22 | Correct | 188 ms | 28308 KB | Output is correct |
23 | Correct | 199 ms | 28388 KB | Output is correct |
24 | Correct | 193 ms | 28332 KB | Output is correct |
25 | Correct | 196 ms | 28388 KB | Output is correct |
26 | Correct | 193 ms | 27844 KB | Output is correct |
27 | Correct | 183 ms | 28652 KB | Output is correct |
28 | Correct | 190 ms | 28384 KB | Output is correct |
29 | Correct | 180 ms | 28700 KB | Output is correct |
30 | Correct | 182 ms | 28308 KB | Output is correct |
31 | Correct | 171 ms | 28656 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9848 KB | Output is correct |
2 | Correct | 11 ms | 10072 KB | Output is correct |
3 | Correct | 11 ms | 9976 KB | Output is correct |
4 | Correct | 10 ms | 9820 KB | Output is correct |
5 | Correct | 11 ms | 9976 KB | Output is correct |
6 | Correct | 11 ms | 10104 KB | Output is correct |
7 | Correct | 10 ms | 9848 KB | Output is correct |
8 | Correct | 10 ms | 9820 KB | Output is correct |
9 | Correct | 11 ms | 10104 KB | Output is correct |
10 | Correct | 11 ms | 10108 KB | Output is correct |
11 | Correct | 11 ms | 10056 KB | Output is correct |
12 | Correct | 11 ms | 9976 KB | Output is correct |
13 | Correct | 11 ms | 10012 KB | Output is correct |
14 | Correct | 11 ms | 10076 KB | Output is correct |
15 | Correct | 12 ms | 10088 KB | Output is correct |
16 | Correct | 247 ms | 25572 KB | Output is correct |
17 | Correct | 786 ms | 39720 KB | Output is correct |
18 | Correct | 56 ms | 13084 KB | Output is correct |
19 | Correct | 232 ms | 28804 KB | Output is correct |
20 | Correct | 772 ms | 39780 KB | Output is correct |
21 | Correct | 419 ms | 31912 KB | Output is correct |
22 | Correct | 245 ms | 31160 KB | Output is correct |
23 | Correct | 937 ms | 39644 KB | Output is correct |
24 | Correct | 783 ms | 39704 KB | Output is correct |
25 | Correct | 798 ms | 39600 KB | Output is correct |
26 | Correct | 228 ms | 28576 KB | Output is correct |
27 | Correct | 232 ms | 28608 KB | Output is correct |
28 | Correct | 224 ms | 28576 KB | Output is correct |
29 | Correct | 226 ms | 28632 KB | Output is correct |
30 | Correct | 230 ms | 28824 KB | Output is correct |
31 | Correct | 10 ms | 9848 KB | Output is correct |
32 | Correct | 10 ms | 9848 KB | Output is correct |
33 | Correct | 10 ms | 9976 KB | Output is correct |
34 | Correct | 10 ms | 9848 KB | Output is correct |
35 | Correct | 10 ms | 9848 KB | Output is correct |
36 | Correct | 10 ms | 9848 KB | Output is correct |
37 | Correct | 10 ms | 9848 KB | Output is correct |
38 | Correct | 10 ms | 9848 KB | Output is correct |
39 | Correct | 10 ms | 9848 KB | Output is correct |
40 | Correct | 10 ms | 9848 KB | Output is correct |
41 | Correct | 395 ms | 31648 KB | Output is correct |
42 | Correct | 771 ms | 39196 KB | Output is correct |
43 | Correct | 762 ms | 39224 KB | Output is correct |
44 | Correct | 185 ms | 28656 KB | Output is correct |
45 | Correct | 767 ms | 39308 KB | Output is correct |
46 | Correct | 800 ms | 39276 KB | Output is correct |
47 | Correct | 792 ms | 39228 KB | Output is correct |
48 | Correct | 769 ms | 39256 KB | Output is correct |
49 | Correct | 787 ms | 39284 KB | Output is correct |
50 | Correct | 791 ms | 39296 KB | Output is correct |
51 | Correct | 739 ms | 39216 KB | Output is correct |
52 | Correct | 751 ms | 39288 KB | Output is correct |
53 | Correct | 734 ms | 39420 KB | Output is correct |
54 | Correct | 786 ms | 39244 KB | Output is correct |
55 | Correct | 790 ms | 39296 KB | Output is correct |
56 | Correct | 780 ms | 39304 KB | Output is correct |
57 | Correct | 785 ms | 39180 KB | Output is correct |
58 | Correct | 763 ms | 39244 KB | Output is correct |
59 | Correct | 194 ms | 30236 KB | Output is correct |
60 | Correct | 735 ms | 39296 KB | Output is correct |
61 | Correct | 633 ms | 39288 KB | Output is correct |
62 | Correct | 188 ms | 28308 KB | Output is correct |
63 | Correct | 199 ms | 28388 KB | Output is correct |
64 | Correct | 193 ms | 28332 KB | Output is correct |
65 | Correct | 196 ms | 28388 KB | Output is correct |
66 | Correct | 193 ms | 27844 KB | Output is correct |
67 | Correct | 183 ms | 28652 KB | Output is correct |
68 | Correct | 190 ms | 28384 KB | Output is correct |
69 | Correct | 180 ms | 28700 KB | Output is correct |
70 | Correct | 182 ms | 28308 KB | Output is correct |
71 | Correct | 171 ms | 28656 KB | Output is correct |
72 | Correct | 467 ms | 32204 KB | Output is correct |
73 | Correct | 801 ms | 39728 KB | Output is correct |
74 | Correct | 814 ms | 39920 KB | Output is correct |
75 | Correct | 784 ms | 40708 KB | Output is correct |
76 | Correct | 800 ms | 40828 KB | Output is correct |
77 | Correct | 814 ms | 40864 KB | Output is correct |
78 | Correct | 800 ms | 40372 KB | Output is correct |
79 | Correct | 779 ms | 39736 KB | Output is correct |
80 | Correct | 801 ms | 39764 KB | Output is correct |
81 | Correct | 788 ms | 39712 KB | Output is correct |
82 | Correct | 818 ms | 39828 KB | Output is correct |
83 | Correct | 811 ms | 39716 KB | Output is correct |
84 | Correct | 796 ms | 39672 KB | Output is correct |
85 | Correct | 788 ms | 39556 KB | Output is correct |
86 | Correct | 763 ms | 39728 KB | Output is correct |
87 | Correct | 788 ms | 39672 KB | Output is correct |
88 | Correct | 794 ms | 39772 KB | Output is correct |
89 | Correct | 217 ms | 31132 KB | Output is correct |
90 | Correct | 792 ms | 39688 KB | Output is correct |
91 | Correct | 665 ms | 39372 KB | Output is correct |
92 | Correct | 399 ms | 28704 KB | Output is correct |
93 | Correct | 383 ms | 29096 KB | Output is correct |
94 | Correct | 410 ms | 28540 KB | Output is correct |
95 | Correct | 405 ms | 28700 KB | Output is correct |
96 | Correct | 393 ms | 28224 KB | Output is correct |
97 | Correct | 345 ms | 29240 KB | Output is correct |
98 | Correct | 391 ms | 28536 KB | Output is correct |
99 | Correct | 272 ms | 29420 KB | Output is correct |
100 | Correct | 392 ms | 29224 KB | Output is correct |