#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
#define v e.first
#define w e.second
const int MAXN = 1e5, INF = 1e18;
vector<vector<pair<int, int>>> g(MAXN);
vector<int> par(MAXN), d(MAXN, INF);
int find(int u){
return par[u] == u ? u : par[u] = find(par[u]);
}
bool comp(int a, int b){
return d[a] > d[b];
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n, m, x, y, z; cin >> n >> m;
while(m--){
cin >> x >> y >> z; --x, --y;
g[x].emplace_back(y, z);
g[y].emplace_back(x, z);
}
priority_queue<pair<int, int>> q;
cin >> z;
while(z--){
cin >> x; --x;
d[x] = 0;
q.emplace(0, x);
}
while(!q.empty()){
int u = q.top().second, dist = -q.top().first; q.pop();
if(dist != d[u]) continue;
for(auto &e : g[u])
if(d[v] > dist + w) q.emplace(-(d[v] = dist + w), v);
}
vector<set<int>> groups(n);
cin >> z;
for(int i=0; i<z; ++i){
cin >> x >> y; --x, --y;
groups[x].insert(i);
groups[y].insert(i);
}
vector<int> cities(n), ans(z);
iota(cities.begin(), cities.end(), 0LL);
sort(cities.begin(), cities.end(), comp);
vector<int> pos(n);
for(int i=0; i<n; ++i) pos[cities[i]] = i;
iota(par.begin(), par.begin()+n, 0LL);
for(int u : cities){
// cout << u+1 sp d[u] sp "..." nl;
z = u;
u = find(u);
for(auto &e : g[u]){
if(pos[v] > pos[z]) continue;
x = find(v);
if(groups[x].size() > groups[u].size()) swap(groups[x], groups[u]);
}
for(auto &e : g[u]){
if(pos[v] > pos[z]) continue;
x = find(v);
if(x == u) continue;
for(int i : groups[x]){
if(groups[u].find(i) != groups[u].end()){
ans[i] = d[u];
// cout << u+1 sp d[u] nl;
}else groups[u].insert(i);
}
par[x] = u;
}
}
for(int i : ans) cout << i nl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4172 KB |
Output is correct |
2 |
Correct |
4 ms |
4428 KB |
Output is correct |
3 |
Correct |
4 ms |
4428 KB |
Output is correct |
4 |
Correct |
3 ms |
4172 KB |
Output is correct |
5 |
Correct |
4 ms |
4412 KB |
Output is correct |
6 |
Correct |
4 ms |
4428 KB |
Output is correct |
7 |
Correct |
3 ms |
4172 KB |
Output is correct |
8 |
Correct |
3 ms |
4172 KB |
Output is correct |
9 |
Correct |
5 ms |
4556 KB |
Output is correct |
10 |
Correct |
4 ms |
4428 KB |
Output is correct |
11 |
Correct |
4 ms |
4556 KB |
Output is correct |
12 |
Correct |
4 ms |
4428 KB |
Output is correct |
13 |
Correct |
4 ms |
4556 KB |
Output is correct |
14 |
Correct |
4 ms |
4556 KB |
Output is correct |
15 |
Correct |
4 ms |
4428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4172 KB |
Output is correct |
2 |
Correct |
4 ms |
4428 KB |
Output is correct |
3 |
Correct |
4 ms |
4428 KB |
Output is correct |
4 |
Correct |
3 ms |
4172 KB |
Output is correct |
5 |
Correct |
4 ms |
4412 KB |
Output is correct |
6 |
Correct |
4 ms |
4428 KB |
Output is correct |
7 |
Correct |
3 ms |
4172 KB |
Output is correct |
8 |
Correct |
3 ms |
4172 KB |
Output is correct |
9 |
Correct |
5 ms |
4556 KB |
Output is correct |
10 |
Correct |
4 ms |
4428 KB |
Output is correct |
11 |
Correct |
4 ms |
4556 KB |
Output is correct |
12 |
Correct |
4 ms |
4428 KB |
Output is correct |
13 |
Correct |
4 ms |
4556 KB |
Output is correct |
14 |
Correct |
4 ms |
4556 KB |
Output is correct |
15 |
Correct |
4 ms |
4428 KB |
Output is correct |
16 |
Correct |
345 ms |
32464 KB |
Output is correct |
17 |
Correct |
860 ms |
51668 KB |
Output is correct |
18 |
Correct |
43 ms |
8720 KB |
Output is correct |
19 |
Correct |
242 ms |
27228 KB |
Output is correct |
20 |
Correct |
785 ms |
51900 KB |
Output is correct |
21 |
Correct |
520 ms |
38592 KB |
Output is correct |
22 |
Correct |
260 ms |
32052 KB |
Output is correct |
23 |
Correct |
778 ms |
61220 KB |
Output is correct |
24 |
Correct |
770 ms |
61092 KB |
Output is correct |
25 |
Correct |
796 ms |
61356 KB |
Output is correct |
26 |
Correct |
244 ms |
30004 KB |
Output is correct |
27 |
Correct |
231 ms |
30044 KB |
Output is correct |
28 |
Correct |
237 ms |
29968 KB |
Output is correct |
29 |
Correct |
236 ms |
30224 KB |
Output is correct |
30 |
Correct |
228 ms |
30132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4172 KB |
Output is correct |
2 |
Correct |
3 ms |
4172 KB |
Output is correct |
3 |
Correct |
3 ms |
4172 KB |
Output is correct |
4 |
Correct |
3 ms |
4172 KB |
Output is correct |
5 |
Correct |
3 ms |
4172 KB |
Output is correct |
6 |
Correct |
3 ms |
4172 KB |
Output is correct |
7 |
Correct |
4 ms |
4172 KB |
Output is correct |
8 |
Correct |
3 ms |
4300 KB |
Output is correct |
9 |
Correct |
3 ms |
4172 KB |
Output is correct |
10 |
Correct |
3 ms |
4172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
238 ms |
22264 KB |
Output is correct |
2 |
Correct |
506 ms |
38492 KB |
Output is correct |
3 |
Correct |
481 ms |
38456 KB |
Output is correct |
4 |
Correct |
81 ms |
15120 KB |
Output is correct |
5 |
Correct |
521 ms |
46764 KB |
Output is correct |
6 |
Correct |
483 ms |
46692 KB |
Output is correct |
7 |
Correct |
560 ms |
46580 KB |
Output is correct |
8 |
Correct |
486 ms |
46664 KB |
Output is correct |
9 |
Correct |
495 ms |
46644 KB |
Output is correct |
10 |
Correct |
493 ms |
46672 KB |
Output is correct |
11 |
Correct |
537 ms |
46652 KB |
Output is correct |
12 |
Correct |
487 ms |
46664 KB |
Output is correct |
13 |
Correct |
490 ms |
46632 KB |
Output is correct |
14 |
Correct |
486 ms |
46632 KB |
Output is correct |
15 |
Correct |
502 ms |
46908 KB |
Output is correct |
16 |
Correct |
512 ms |
46736 KB |
Output is correct |
17 |
Correct |
495 ms |
46656 KB |
Output is correct |
18 |
Correct |
515 ms |
46696 KB |
Output is correct |
19 |
Correct |
78 ms |
16840 KB |
Output is correct |
20 |
Correct |
493 ms |
46740 KB |
Output is correct |
21 |
Correct |
452 ms |
46524 KB |
Output is correct |
22 |
Correct |
132 ms |
18356 KB |
Output is correct |
23 |
Correct |
95 ms |
17232 KB |
Output is correct |
24 |
Correct |
103 ms |
18304 KB |
Output is correct |
25 |
Correct |
103 ms |
18360 KB |
Output is correct |
26 |
Correct |
113 ms |
17336 KB |
Output is correct |
27 |
Correct |
81 ms |
16756 KB |
Output is correct |
28 |
Correct |
108 ms |
18284 KB |
Output is correct |
29 |
Correct |
103 ms |
16812 KB |
Output is correct |
30 |
Correct |
110 ms |
18316 KB |
Output is correct |
31 |
Correct |
85 ms |
16764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4172 KB |
Output is correct |
2 |
Correct |
4 ms |
4428 KB |
Output is correct |
3 |
Correct |
4 ms |
4428 KB |
Output is correct |
4 |
Correct |
3 ms |
4172 KB |
Output is correct |
5 |
Correct |
4 ms |
4412 KB |
Output is correct |
6 |
Correct |
4 ms |
4428 KB |
Output is correct |
7 |
Correct |
3 ms |
4172 KB |
Output is correct |
8 |
Correct |
3 ms |
4172 KB |
Output is correct |
9 |
Correct |
5 ms |
4556 KB |
Output is correct |
10 |
Correct |
4 ms |
4428 KB |
Output is correct |
11 |
Correct |
4 ms |
4556 KB |
Output is correct |
12 |
Correct |
4 ms |
4428 KB |
Output is correct |
13 |
Correct |
4 ms |
4556 KB |
Output is correct |
14 |
Correct |
4 ms |
4556 KB |
Output is correct |
15 |
Correct |
4 ms |
4428 KB |
Output is correct |
16 |
Correct |
345 ms |
32464 KB |
Output is correct |
17 |
Correct |
860 ms |
51668 KB |
Output is correct |
18 |
Correct |
43 ms |
8720 KB |
Output is correct |
19 |
Correct |
242 ms |
27228 KB |
Output is correct |
20 |
Correct |
785 ms |
51900 KB |
Output is correct |
21 |
Correct |
520 ms |
38592 KB |
Output is correct |
22 |
Correct |
260 ms |
32052 KB |
Output is correct |
23 |
Correct |
778 ms |
61220 KB |
Output is correct |
24 |
Correct |
770 ms |
61092 KB |
Output is correct |
25 |
Correct |
796 ms |
61356 KB |
Output is correct |
26 |
Correct |
244 ms |
30004 KB |
Output is correct |
27 |
Correct |
231 ms |
30044 KB |
Output is correct |
28 |
Correct |
237 ms |
29968 KB |
Output is correct |
29 |
Correct |
236 ms |
30224 KB |
Output is correct |
30 |
Correct |
228 ms |
30132 KB |
Output is correct |
31 |
Correct |
3 ms |
4172 KB |
Output is correct |
32 |
Correct |
3 ms |
4172 KB |
Output is correct |
33 |
Correct |
3 ms |
4172 KB |
Output is correct |
34 |
Correct |
3 ms |
4172 KB |
Output is correct |
35 |
Correct |
3 ms |
4172 KB |
Output is correct |
36 |
Correct |
3 ms |
4172 KB |
Output is correct |
37 |
Correct |
4 ms |
4172 KB |
Output is correct |
38 |
Correct |
3 ms |
4300 KB |
Output is correct |
39 |
Correct |
3 ms |
4172 KB |
Output is correct |
40 |
Correct |
3 ms |
4172 KB |
Output is correct |
41 |
Correct |
238 ms |
22264 KB |
Output is correct |
42 |
Correct |
506 ms |
38492 KB |
Output is correct |
43 |
Correct |
481 ms |
38456 KB |
Output is correct |
44 |
Correct |
81 ms |
15120 KB |
Output is correct |
45 |
Correct |
521 ms |
46764 KB |
Output is correct |
46 |
Correct |
483 ms |
46692 KB |
Output is correct |
47 |
Correct |
560 ms |
46580 KB |
Output is correct |
48 |
Correct |
486 ms |
46664 KB |
Output is correct |
49 |
Correct |
495 ms |
46644 KB |
Output is correct |
50 |
Correct |
493 ms |
46672 KB |
Output is correct |
51 |
Correct |
537 ms |
46652 KB |
Output is correct |
52 |
Correct |
487 ms |
46664 KB |
Output is correct |
53 |
Correct |
490 ms |
46632 KB |
Output is correct |
54 |
Correct |
486 ms |
46632 KB |
Output is correct |
55 |
Correct |
502 ms |
46908 KB |
Output is correct |
56 |
Correct |
512 ms |
46736 KB |
Output is correct |
57 |
Correct |
495 ms |
46656 KB |
Output is correct |
58 |
Correct |
515 ms |
46696 KB |
Output is correct |
59 |
Correct |
78 ms |
16840 KB |
Output is correct |
60 |
Correct |
493 ms |
46740 KB |
Output is correct |
61 |
Correct |
452 ms |
46524 KB |
Output is correct |
62 |
Correct |
132 ms |
18356 KB |
Output is correct |
63 |
Correct |
95 ms |
17232 KB |
Output is correct |
64 |
Correct |
103 ms |
18304 KB |
Output is correct |
65 |
Correct |
103 ms |
18360 KB |
Output is correct |
66 |
Correct |
113 ms |
17336 KB |
Output is correct |
67 |
Correct |
81 ms |
16756 KB |
Output is correct |
68 |
Correct |
108 ms |
18284 KB |
Output is correct |
69 |
Correct |
103 ms |
16812 KB |
Output is correct |
70 |
Correct |
110 ms |
18316 KB |
Output is correct |
71 |
Correct |
85 ms |
16764 KB |
Output is correct |
72 |
Correct |
573 ms |
44056 KB |
Output is correct |
73 |
Correct |
809 ms |
61476 KB |
Output is correct |
74 |
Correct |
807 ms |
61400 KB |
Output is correct |
75 |
Correct |
858 ms |
61496 KB |
Output is correct |
76 |
Correct |
829 ms |
61388 KB |
Output is correct |
77 |
Correct |
833 ms |
61528 KB |
Output is correct |
78 |
Correct |
842 ms |
61392 KB |
Output is correct |
79 |
Correct |
787 ms |
61420 KB |
Output is correct |
80 |
Correct |
854 ms |
61380 KB |
Output is correct |
81 |
Correct |
799 ms |
61368 KB |
Output is correct |
82 |
Correct |
780 ms |
61392 KB |
Output is correct |
83 |
Correct |
793 ms |
61324 KB |
Output is correct |
84 |
Correct |
802 ms |
61444 KB |
Output is correct |
85 |
Correct |
814 ms |
61576 KB |
Output is correct |
86 |
Correct |
813 ms |
61428 KB |
Output is correct |
87 |
Correct |
787 ms |
61460 KB |
Output is correct |
88 |
Correct |
847 ms |
61360 KB |
Output is correct |
89 |
Correct |
306 ms |
33796 KB |
Output is correct |
90 |
Correct |
815 ms |
61372 KB |
Output is correct |
91 |
Correct |
742 ms |
61048 KB |
Output is correct |
92 |
Correct |
364 ms |
34708 KB |
Output is correct |
93 |
Correct |
417 ms |
58652 KB |
Output is correct |
94 |
Correct |
340 ms |
34612 KB |
Output is correct |
95 |
Correct |
319 ms |
34816 KB |
Output is correct |
96 |
Correct |
475 ms |
61044 KB |
Output is correct |
97 |
Correct |
365 ms |
36932 KB |
Output is correct |
98 |
Correct |
326 ms |
34612 KB |
Output is correct |
99 |
Correct |
343 ms |
36892 KB |
Output is correct |
100 |
Correct |
327 ms |
34820 KB |
Output is correct |