# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
92370 | 2019-01-02T16:22:09 Z | Nodir_Bobiev | Evacuation plan (IZhO18_plan) | C++14 | 1016 ms | 62468 KB |
# include <iostream> # include <vector> # include <set> # include <queue> # include <numeric> using namespace std; const int N = 1e5 + 100; int n, k, m, Q; int dist[N], S[N], T[N], p[N], ans[N]; bool used[N]; vector < pair < int, int > > gr[N]; queue < int > q; set < pair < int, int > > st; set < int > IDS[N]; int FIND(int x){ if(p[x] == x)return x; else return p[x] = FIND(p[x]); } void union_sets(int x, int y, int ds) { x = FIND(x); y = FIND(y); if(x == y)return; if((int)IDS[x].size() > (int)IDS[y].size())swap(x, y); for (auto id: IDS[x]){ if(ans[id] == -1 && IDS[y].find(id) != IDS[y].end()) ans[id] = ds; } for(auto id: IDS[x]) IDS[y].insert(id); p[x] = y; } int main() { scanf("%d %d", &n, &m); while(m--){ int a, b, w; scanf("%d %d %d", &a,&b, &w); gr[a].push_back({w, b}); gr[b].push_back({w, a}); } fill(dist, dist + N, 1e8); fill(ans, ans + N, -1); iota(p, p + N, 0); scanf("%d", &k); while(k--){ int a; scanf("%d", &a); dist[a] = 0; q.push(a); } while(!q.empty()){ int v = q.front(); q.pop(); for(auto to: gr[v]){ if(dist[to.second] > dist[v] + to.first){ dist[to.second] = dist[v] + to.first; q.push(to.second); } } } for (int i = 1; i <= n; i++) st.insert({-dist[i], i}); scanf("%d", &Q); for (int i = 1; i <= Q; i++){ scanf("%d %d", S + i, T + i); IDS[S[i]].insert(i); IDS[T[i]].insert(i); } for (auto it = st.begin(); it != st.end(); it++){ int v = it -> second; used[v] = true; for(auto to: gr[v]){ if(used[to.second]) union_sets(to.second, v, dist[v]); } } for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]); } /* 9 12 1 9 4 1 2 5 2 3 7 2 4 3 4 3 6 3 6 4 8 7 10 6 7 5 5 8 1 9 5 7 5 4 12 6 8 2 2 4 7 5 1 6 5 3 4 8 5 8 1 5 */
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 8568 KB | Output is correct |
2 | Correct | 10 ms | 8796 KB | Output is correct |
3 | Correct | 11 ms | 8676 KB | Output is correct |
4 | Correct | 9 ms | 8568 KB | Output is correct |
5 | Correct | 10 ms | 8696 KB | Output is correct |
6 | Correct | 10 ms | 8696 KB | Output is correct |
7 | Correct | 9 ms | 8568 KB | Output is correct |
8 | Correct | 9 ms | 8568 KB | Output is correct |
9 | Correct | 11 ms | 8824 KB | Output is correct |
10 | Correct | 11 ms | 8824 KB | Output is correct |
11 | Correct | 11 ms | 8824 KB | Output is correct |
12 | Correct | 10 ms | 8696 KB | Output is correct |
13 | Correct | 11 ms | 8824 KB | Output is correct |
14 | Correct | 10 ms | 8796 KB | Output is correct |
15 | Correct | 10 ms | 8852 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 8568 KB | Output is correct |
2 | Correct | 10 ms | 8796 KB | Output is correct |
3 | Correct | 11 ms | 8676 KB | Output is correct |
4 | Correct | 9 ms | 8568 KB | Output is correct |
5 | Correct | 10 ms | 8696 KB | Output is correct |
6 | Correct | 10 ms | 8696 KB | Output is correct |
7 | Correct | 9 ms | 8568 KB | Output is correct |
8 | Correct | 9 ms | 8568 KB | Output is correct |
9 | Correct | 11 ms | 8824 KB | Output is correct |
10 | Correct | 11 ms | 8824 KB | Output is correct |
11 | Correct | 11 ms | 8824 KB | Output is correct |
12 | Correct | 10 ms | 8696 KB | Output is correct |
13 | Correct | 11 ms | 8824 KB | Output is correct |
14 | Correct | 10 ms | 8796 KB | Output is correct |
15 | Correct | 10 ms | 8852 KB | Output is correct |
16 | Correct | 423 ms | 34064 KB | Output is correct |
17 | Correct | 931 ms | 45568 KB | Output is correct |
18 | Correct | 57 ms | 12664 KB | Output is correct |
19 | Correct | 315 ms | 30780 KB | Output is correct |
20 | Correct | 906 ms | 46816 KB | Output is correct |
21 | Correct | 515 ms | 39664 KB | Output is correct |
22 | Correct | 385 ms | 35128 KB | Output is correct |
23 | Correct | 912 ms | 46460 KB | Output is correct |
24 | Correct | 900 ms | 48252 KB | Output is correct |
25 | Correct | 831 ms | 48732 KB | Output is correct |
26 | Correct | 322 ms | 30560 KB | Output is correct |
27 | Correct | 319 ms | 30712 KB | Output is correct |
28 | Correct | 322 ms | 30572 KB | Output is correct |
29 | Correct | 312 ms | 30700 KB | Output is correct |
30 | Correct | 325 ms | 30772 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 8568 KB | Output is correct |
2 | Correct | 9 ms | 8568 KB | Output is correct |
3 | Correct | 9 ms | 8568 KB | Output is correct |
4 | Correct | 9 ms | 8560 KB | Output is correct |
5 | Correct | 9 ms | 8568 KB | Output is correct |
6 | Correct | 9 ms | 8568 KB | Output is correct |
7 | Correct | 9 ms | 8568 KB | Output is correct |
8 | Correct | 9 ms | 8568 KB | Output is correct |
9 | Correct | 9 ms | 8568 KB | Output is correct |
10 | Correct | 9 ms | 8568 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 269 ms | 19708 KB | Output is correct |
2 | Correct | 571 ms | 26204 KB | Output is correct |
3 | Correct | 607 ms | 26120 KB | Output is correct |
4 | Correct | 161 ms | 16632 KB | Output is correct |
5 | Correct | 604 ms | 26232 KB | Output is correct |
6 | Correct | 573 ms | 26352 KB | Output is correct |
7 | Correct | 604 ms | 26272 KB | Output is correct |
8 | Correct | 576 ms | 26196 KB | Output is correct |
9 | Correct | 554 ms | 26228 KB | Output is correct |
10 | Correct | 594 ms | 26236 KB | Output is correct |
11 | Correct | 584 ms | 26176 KB | Output is correct |
12 | Correct | 570 ms | 26220 KB | Output is correct |
13 | Correct | 562 ms | 26232 KB | Output is correct |
14 | Correct | 550 ms | 26320 KB | Output is correct |
15 | Correct | 571 ms | 26360 KB | Output is correct |
16 | Correct | 537 ms | 26164 KB | Output is correct |
17 | Correct | 534 ms | 26120 KB | Output is correct |
18 | Correct | 557 ms | 26360 KB | Output is correct |
19 | Correct | 150 ms | 16504 KB | Output is correct |
20 | Correct | 581 ms | 26416 KB | Output is correct |
21 | Correct | 493 ms | 26192 KB | Output is correct |
22 | Correct | 127 ms | 17324 KB | Output is correct |
23 | Correct | 141 ms | 16940 KB | Output is correct |
24 | Correct | 128 ms | 17328 KB | Output is correct |
25 | Correct | 131 ms | 17288 KB | Output is correct |
26 | Correct | 162 ms | 17144 KB | Output is correct |
27 | Correct | 158 ms | 16504 KB | Output is correct |
28 | Correct | 169 ms | 17352 KB | Output is correct |
29 | Correct | 186 ms | 16440 KB | Output is correct |
30 | Correct | 121 ms | 17352 KB | Output is correct |
31 | Correct | 152 ms | 16424 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 8568 KB | Output is correct |
2 | Correct | 10 ms | 8796 KB | Output is correct |
3 | Correct | 11 ms | 8676 KB | Output is correct |
4 | Correct | 9 ms | 8568 KB | Output is correct |
5 | Correct | 10 ms | 8696 KB | Output is correct |
6 | Correct | 10 ms | 8696 KB | Output is correct |
7 | Correct | 9 ms | 8568 KB | Output is correct |
8 | Correct | 9 ms | 8568 KB | Output is correct |
9 | Correct | 11 ms | 8824 KB | Output is correct |
10 | Correct | 11 ms | 8824 KB | Output is correct |
11 | Correct | 11 ms | 8824 KB | Output is correct |
12 | Correct | 10 ms | 8696 KB | Output is correct |
13 | Correct | 11 ms | 8824 KB | Output is correct |
14 | Correct | 10 ms | 8796 KB | Output is correct |
15 | Correct | 10 ms | 8852 KB | Output is correct |
16 | Correct | 423 ms | 34064 KB | Output is correct |
17 | Correct | 931 ms | 45568 KB | Output is correct |
18 | Correct | 57 ms | 12664 KB | Output is correct |
19 | Correct | 315 ms | 30780 KB | Output is correct |
20 | Correct | 906 ms | 46816 KB | Output is correct |
21 | Correct | 515 ms | 39664 KB | Output is correct |
22 | Correct | 385 ms | 35128 KB | Output is correct |
23 | Correct | 912 ms | 46460 KB | Output is correct |
24 | Correct | 900 ms | 48252 KB | Output is correct |
25 | Correct | 831 ms | 48732 KB | Output is correct |
26 | Correct | 322 ms | 30560 KB | Output is correct |
27 | Correct | 319 ms | 30712 KB | Output is correct |
28 | Correct | 322 ms | 30572 KB | Output is correct |
29 | Correct | 312 ms | 30700 KB | Output is correct |
30 | Correct | 325 ms | 30772 KB | Output is correct |
31 | Correct | 9 ms | 8568 KB | Output is correct |
32 | Correct | 9 ms | 8568 KB | Output is correct |
33 | Correct | 9 ms | 8568 KB | Output is correct |
34 | Correct | 9 ms | 8560 KB | Output is correct |
35 | Correct | 9 ms | 8568 KB | Output is correct |
36 | Correct | 9 ms | 8568 KB | Output is correct |
37 | Correct | 9 ms | 8568 KB | Output is correct |
38 | Correct | 9 ms | 8568 KB | Output is correct |
39 | Correct | 9 ms | 8568 KB | Output is correct |
40 | Correct | 9 ms | 8568 KB | Output is correct |
41 | Correct | 269 ms | 19708 KB | Output is correct |
42 | Correct | 571 ms | 26204 KB | Output is correct |
43 | Correct | 607 ms | 26120 KB | Output is correct |
44 | Correct | 161 ms | 16632 KB | Output is correct |
45 | Correct | 604 ms | 26232 KB | Output is correct |
46 | Correct | 573 ms | 26352 KB | Output is correct |
47 | Correct | 604 ms | 26272 KB | Output is correct |
48 | Correct | 576 ms | 26196 KB | Output is correct |
49 | Correct | 554 ms | 26228 KB | Output is correct |
50 | Correct | 594 ms | 26236 KB | Output is correct |
51 | Correct | 584 ms | 26176 KB | Output is correct |
52 | Correct | 570 ms | 26220 KB | Output is correct |
53 | Correct | 562 ms | 26232 KB | Output is correct |
54 | Correct | 550 ms | 26320 KB | Output is correct |
55 | Correct | 571 ms | 26360 KB | Output is correct |
56 | Correct | 537 ms | 26164 KB | Output is correct |
57 | Correct | 534 ms | 26120 KB | Output is correct |
58 | Correct | 557 ms | 26360 KB | Output is correct |
59 | Correct | 150 ms | 16504 KB | Output is correct |
60 | Correct | 581 ms | 26416 KB | Output is correct |
61 | Correct | 493 ms | 26192 KB | Output is correct |
62 | Correct | 127 ms | 17324 KB | Output is correct |
63 | Correct | 141 ms | 16940 KB | Output is correct |
64 | Correct | 128 ms | 17328 KB | Output is correct |
65 | Correct | 131 ms | 17288 KB | Output is correct |
66 | Correct | 162 ms | 17144 KB | Output is correct |
67 | Correct | 158 ms | 16504 KB | Output is correct |
68 | Correct | 169 ms | 17352 KB | Output is correct |
69 | Correct | 186 ms | 16440 KB | Output is correct |
70 | Correct | 121 ms | 17352 KB | Output is correct |
71 | Correct | 152 ms | 16424 KB | Output is correct |
72 | Correct | 566 ms | 41324 KB | Output is correct |
73 | Correct | 893 ms | 46168 KB | Output is correct |
74 | Correct | 1004 ms | 45936 KB | Output is correct |
75 | Correct | 915 ms | 47004 KB | Output is correct |
76 | Correct | 907 ms | 46460 KB | Output is correct |
77 | Correct | 885 ms | 47648 KB | Output is correct |
78 | Correct | 910 ms | 46992 KB | Output is correct |
79 | Correct | 918 ms | 47788 KB | Output is correct |
80 | Correct | 1006 ms | 48380 KB | Output is correct |
81 | Correct | 955 ms | 46504 KB | Output is correct |
82 | Correct | 868 ms | 46844 KB | Output is correct |
83 | Correct | 866 ms | 47384 KB | Output is correct |
84 | Correct | 857 ms | 46196 KB | Output is correct |
85 | Correct | 866 ms | 46536 KB | Output is correct |
86 | Correct | 869 ms | 45992 KB | Output is correct |
87 | Correct | 903 ms | 46820 KB | Output is correct |
88 | Correct | 914 ms | 46296 KB | Output is correct |
89 | Correct | 439 ms | 35276 KB | Output is correct |
90 | Correct | 1016 ms | 46012 KB | Output is correct |
91 | Correct | 799 ms | 45976 KB | Output is correct |
92 | Correct | 392 ms | 35336 KB | Output is correct |
93 | Correct | 587 ms | 61340 KB | Output is correct |
94 | Correct | 397 ms | 35216 KB | Output is correct |
95 | Correct | 406 ms | 35352 KB | Output is correct |
96 | Correct | 645 ms | 62468 KB | Output is correct |
97 | Correct | 502 ms | 38288 KB | Output is correct |
98 | Correct | 402 ms | 35208 KB | Output is correct |
99 | Correct | 505 ms | 38344 KB | Output is correct |
100 | Correct | 422 ms | 35280 KB | Output is correct |