#include <bits/stdc++.h>
using namespace std;
struct DSU
{
vector<int> rt, sz;
vector<int> stk;
DSU(int n)
{
rt.resize(n);
sz.resize(n, 1);
iota(rt.begin(), rt.end(), 0);
}
int find(int u)
{
if (u == rt[u]) return u;
return find(rt[u]);
}
bool same(int u, int v)
{
return find(u) == find(v);
}
void unite(int u, int v)
{
u = find(u), v = find(v);
if (u == v)
{
stk.push_back(-1);
return;
}
if (sz[u] < sz[v])
swap(u, v);
stk.push_back(v);
rt[v] = u;
sz[u] += sz[v];
}
void rollback()
{
int v = stk.back();
stk.pop_back();
if (v == -1) return;
int u = rt[v];
sz[u] -= sz[v];
rt[v] = v;
}
};
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
vector<vector<pair<int, int>>> g(n);
for (int i = 0; i < m; i++)
{
int u, v, w; cin >> u >> v >> w;
u--, v--;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
vector<int> a(n);
{
int k; cin >> k;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
for (int i = 0; i < k; i++)
{
int x; cin >> x;
x--;
pq.emplace(0, x);
}
vector<bool> vis(n);
while (pq.size())
{
auto [x, u] = pq.top();
pq.pop();
if (vis[u]) continue;
vis[u] = 1;
a[u] = x;
for (auto &[v, w] : g[u])
{
pq.emplace(x + w, v);
}
}
}
int q; cin >> q;
vector<pair<int, int>> qry(q);
for (int i = 0; i < q; i++)
{
int u, v; cin >> u >> v;
u--, v--;
qry[i] = make_pair(u, v);
}
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j)
{
return a[i] < a[j];
});
DSU dsu(n);
vector<int> vis(n);
vector<int> ans(q, -1);
function<void(vector<int> &, int, int)> solve = [&](vector<int> &qqry, int l, int r)
{
if (l == r - 1)
{
for (int i : qqry)
ans[i] = a[ord[l]];
return;
}
int mid = (l + r) / 2;
vector<int> lqry, rqry;
for (int i = r - 1; i >= mid; i--)
{
int u = ord[i];
vis[u] = 1;
for (auto &[v, w] : g[u])
if (vis[v])
dsu.unite(u, v);
}
for (int j : qqry)
if (dsu.same(qry[j].first, qry[j].second))
rqry.push_back(j);
else
lqry.push_back(j);
solve(lqry, l, mid);
for (int i = mid; i < r; i++)
{
int u = ord[i];
for (auto &[v, w] : g[u])
if (vis[v])
dsu.rollback();
vis[u] = 0;
}
solve(rqry, mid, r);
};
vector<int> qqry(q);
iota(qqry.begin(), qqry.end(), 0);
solve(qqry, 0, n);
for (int i = 0; i < q; i++)
cout << ans[i] << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
572 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
572 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
180 ms |
10980 KB |
Output is correct |
17 |
Correct |
598 ms |
26704 KB |
Output is correct |
18 |
Correct |
35 ms |
2700 KB |
Output is correct |
19 |
Correct |
99 ms |
18012 KB |
Output is correct |
20 |
Correct |
585 ms |
26700 KB |
Output is correct |
21 |
Correct |
277 ms |
15544 KB |
Output is correct |
22 |
Correct |
103 ms |
11232 KB |
Output is correct |
23 |
Correct |
546 ms |
25800 KB |
Output is correct |
24 |
Correct |
576 ms |
26328 KB |
Output is correct |
25 |
Correct |
572 ms |
27100 KB |
Output is correct |
26 |
Correct |
114 ms |
18008 KB |
Output is correct |
27 |
Correct |
101 ms |
17548 KB |
Output is correct |
28 |
Correct |
104 ms |
18032 KB |
Output is correct |
29 |
Correct |
111 ms |
18032 KB |
Output is correct |
30 |
Correct |
102 ms |
18128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
13056 KB |
Output is correct |
2 |
Correct |
511 ms |
27096 KB |
Output is correct |
3 |
Correct |
501 ms |
25784 KB |
Output is correct |
4 |
Correct |
58 ms |
8652 KB |
Output is correct |
5 |
Correct |
502 ms |
26964 KB |
Output is correct |
6 |
Correct |
514 ms |
26816 KB |
Output is correct |
7 |
Correct |
519 ms |
26020 KB |
Output is correct |
8 |
Correct |
534 ms |
26692 KB |
Output is correct |
9 |
Correct |
498 ms |
26568 KB |
Output is correct |
10 |
Correct |
519 ms |
26604 KB |
Output is correct |
11 |
Correct |
524 ms |
27296 KB |
Output is correct |
12 |
Correct |
504 ms |
25500 KB |
Output is correct |
13 |
Correct |
498 ms |
25688 KB |
Output is correct |
14 |
Correct |
513 ms |
25868 KB |
Output is correct |
15 |
Correct |
481 ms |
26576 KB |
Output is correct |
16 |
Correct |
527 ms |
25940 KB |
Output is correct |
17 |
Correct |
511 ms |
25472 KB |
Output is correct |
18 |
Correct |
482 ms |
25908 KB |
Output is correct |
19 |
Correct |
58 ms |
8408 KB |
Output is correct |
20 |
Correct |
528 ms |
25660 KB |
Output is correct |
21 |
Correct |
510 ms |
25824 KB |
Output is correct |
22 |
Correct |
91 ms |
9532 KB |
Output is correct |
23 |
Correct |
86 ms |
8908 KB |
Output is correct |
24 |
Correct |
72 ms |
9324 KB |
Output is correct |
25 |
Correct |
87 ms |
9816 KB |
Output is correct |
26 |
Correct |
93 ms |
9144 KB |
Output is correct |
27 |
Correct |
57 ms |
8408 KB |
Output is correct |
28 |
Correct |
83 ms |
9528 KB |
Output is correct |
29 |
Correct |
57 ms |
8516 KB |
Output is correct |
30 |
Correct |
79 ms |
9544 KB |
Output is correct |
31 |
Correct |
59 ms |
8408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
604 KB |
Output is correct |
3 |
Correct |
1 ms |
604 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
572 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
180 ms |
10980 KB |
Output is correct |
17 |
Correct |
598 ms |
26704 KB |
Output is correct |
18 |
Correct |
35 ms |
2700 KB |
Output is correct |
19 |
Correct |
99 ms |
18012 KB |
Output is correct |
20 |
Correct |
585 ms |
26700 KB |
Output is correct |
21 |
Correct |
277 ms |
15544 KB |
Output is correct |
22 |
Correct |
103 ms |
11232 KB |
Output is correct |
23 |
Correct |
546 ms |
25800 KB |
Output is correct |
24 |
Correct |
576 ms |
26328 KB |
Output is correct |
25 |
Correct |
572 ms |
27100 KB |
Output is correct |
26 |
Correct |
114 ms |
18008 KB |
Output is correct |
27 |
Correct |
101 ms |
17548 KB |
Output is correct |
28 |
Correct |
104 ms |
18032 KB |
Output is correct |
29 |
Correct |
111 ms |
18032 KB |
Output is correct |
30 |
Correct |
102 ms |
18128 KB |
Output is correct |
31 |
Correct |
0 ms |
344 KB |
Output is correct |
32 |
Correct |
0 ms |
344 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
0 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
0 ms |
348 KB |
Output is correct |
41 |
Correct |
231 ms |
13056 KB |
Output is correct |
42 |
Correct |
511 ms |
27096 KB |
Output is correct |
43 |
Correct |
501 ms |
25784 KB |
Output is correct |
44 |
Correct |
58 ms |
8652 KB |
Output is correct |
45 |
Correct |
502 ms |
26964 KB |
Output is correct |
46 |
Correct |
514 ms |
26816 KB |
Output is correct |
47 |
Correct |
519 ms |
26020 KB |
Output is correct |
48 |
Correct |
534 ms |
26692 KB |
Output is correct |
49 |
Correct |
498 ms |
26568 KB |
Output is correct |
50 |
Correct |
519 ms |
26604 KB |
Output is correct |
51 |
Correct |
524 ms |
27296 KB |
Output is correct |
52 |
Correct |
504 ms |
25500 KB |
Output is correct |
53 |
Correct |
498 ms |
25688 KB |
Output is correct |
54 |
Correct |
513 ms |
25868 KB |
Output is correct |
55 |
Correct |
481 ms |
26576 KB |
Output is correct |
56 |
Correct |
527 ms |
25940 KB |
Output is correct |
57 |
Correct |
511 ms |
25472 KB |
Output is correct |
58 |
Correct |
482 ms |
25908 KB |
Output is correct |
59 |
Correct |
58 ms |
8408 KB |
Output is correct |
60 |
Correct |
528 ms |
25660 KB |
Output is correct |
61 |
Correct |
510 ms |
25824 KB |
Output is correct |
62 |
Correct |
91 ms |
9532 KB |
Output is correct |
63 |
Correct |
86 ms |
8908 KB |
Output is correct |
64 |
Correct |
72 ms |
9324 KB |
Output is correct |
65 |
Correct |
87 ms |
9816 KB |
Output is correct |
66 |
Correct |
93 ms |
9144 KB |
Output is correct |
67 |
Correct |
57 ms |
8408 KB |
Output is correct |
68 |
Correct |
83 ms |
9528 KB |
Output is correct |
69 |
Correct |
57 ms |
8516 KB |
Output is correct |
70 |
Correct |
79 ms |
9544 KB |
Output is correct |
71 |
Correct |
59 ms |
8408 KB |
Output is correct |
72 |
Correct |
291 ms |
20404 KB |
Output is correct |
73 |
Correct |
588 ms |
35956 KB |
Output is correct |
74 |
Correct |
561 ms |
34544 KB |
Output is correct |
75 |
Correct |
561 ms |
34752 KB |
Output is correct |
76 |
Correct |
560 ms |
34480 KB |
Output is correct |
77 |
Correct |
567 ms |
34756 KB |
Output is correct |
78 |
Correct |
572 ms |
35404 KB |
Output is correct |
79 |
Correct |
564 ms |
34760 KB |
Output is correct |
80 |
Correct |
564 ms |
35008 KB |
Output is correct |
81 |
Correct |
592 ms |
34540 KB |
Output is correct |
82 |
Correct |
552 ms |
34788 KB |
Output is correct |
83 |
Correct |
551 ms |
34368 KB |
Output is correct |
84 |
Correct |
553 ms |
35536 KB |
Output is correct |
85 |
Correct |
580 ms |
34580 KB |
Output is correct |
86 |
Correct |
546 ms |
35736 KB |
Output is correct |
87 |
Correct |
556 ms |
34292 KB |
Output is correct |
88 |
Correct |
589 ms |
34836 KB |
Output is correct |
89 |
Correct |
106 ms |
14052 KB |
Output is correct |
90 |
Correct |
538 ms |
34376 KB |
Output is correct |
91 |
Correct |
546 ms |
36032 KB |
Output is correct |
92 |
Correct |
96 ms |
21312 KB |
Output is correct |
93 |
Correct |
166 ms |
15412 KB |
Output is correct |
94 |
Correct |
97 ms |
20564 KB |
Output is correct |
95 |
Correct |
109 ms |
20796 KB |
Output is correct |
96 |
Correct |
175 ms |
18928 KB |
Output is correct |
97 |
Correct |
99 ms |
16736 KB |
Output is correct |
98 |
Correct |
125 ms |
21088 KB |
Output is correct |
99 |
Correct |
100 ms |
16868 KB |
Output is correct |
100 |
Correct |
94 ms |
20536 KB |
Output is correct |