#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using namespace std;
const int MAXN = 200001;
int dp[MAXN];
using Pair = pair<int, int>;
set <Pair> s;
vector<pair<int, int> > gid[MAXN];
vector<int> g[MAXN];
vector<pair<int, int>> e[MAXN];
constexpr int INF = 1 << 30;
void upd(int x, int y) {
if (dp[x] < y) {
return;
}
s.erase({ dp[x], x });
dp[x] = y;
s.emplace(y, x);
}
int dist(int a, int b) {
int l = 0, r = min(gid[a].size(), gid[b].size());
while (l < r) {
int m = (l + r) / 2;
if (gid[a][m] == gid[b][m]) {
l = m + 1;
} else {
r = m;
}
}
int ans = 0;
for (int i = max(l - 1, 0); i <= l; ++i) {
for (int j = max(l - 1, 0); j <= l; ++j) {
if (gid[a][i].first == gid[b][j].first) {
ans = max(ans, min(gid[a][i].second, gid[b][j].second));
}
}
}
return ans;
}
vector <pair<int, pair<int, int>>> edges;
int main() {
#ifdef PAUNSVOKNO
freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20); cout.tie(nullptr); cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
g[i] = { i };
gid[i] = {{i, INF} };
}
fill(dp + 1, dp + n + 1, INF);
for (int i = 0; i < m; ++i) {
int a, b, w;
cin >> a >> b >> w;
e[a].emplace_back(b, w);
e[b].emplace_back(a, w);
}
int cities;
cin >> cities;
for (int i = 0; i < cities; ++i) {
int v;
cin >> v;
upd(v, 0);
}
while (!s.empty()) {
int v = s.begin()->second;
s.erase(s.begin());
for (auto ed : e[v]) {
upd(ed.first, dp[v] + ed.second);
}
}
for (int i = 1; i <= n; ++i) {
for (auto ed : e[i]) {
if (ed.first > i) {
edges.push_back({ min(dp[i], dp[ed.first]), {i, ed.first} });
}
}
}
sort(edges.begin(), edges.end());
reverse(edges.begin(), edges.end());
for (auto& edge : edges) {
int v = edge.second.first;
int u = edge.second.second;
int gv = gid[v].back().first;
int gu = gid[u].back().first;
if (gv != gu) {
if (g[gv].size() > g[gu].size()) {
swap(gv, gu);
}
for (int ver : g[gv]) {
gid[ver].emplace_back(gu, edge.first);
g[gu].push_back(ver);
}
g[gv].clear();
}
}
for (int i = 1; i <= n; ++i) {
reverse(gid[i].begin(), gid[i].end());
}
ll sum = 0;
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int a, b;
cin >> a >> b;
cout << dist(a, b) << endl;
}
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:129:8: warning: unused variable 'sum' [-Wunused-variable]
ll sum = 0;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14456 KB |
Output is correct |
2 |
Correct |
18 ms |
14584 KB |
Output is correct |
3 |
Correct |
18 ms |
14556 KB |
Output is correct |
4 |
Correct |
14 ms |
14432 KB |
Output is correct |
5 |
Correct |
18 ms |
14584 KB |
Output is correct |
6 |
Correct |
18 ms |
14584 KB |
Output is correct |
7 |
Correct |
15 ms |
14456 KB |
Output is correct |
8 |
Correct |
15 ms |
14460 KB |
Output is correct |
9 |
Correct |
19 ms |
14584 KB |
Output is correct |
10 |
Correct |
19 ms |
14584 KB |
Output is correct |
11 |
Correct |
19 ms |
14588 KB |
Output is correct |
12 |
Correct |
18 ms |
14584 KB |
Output is correct |
13 |
Correct |
19 ms |
14584 KB |
Output is correct |
14 |
Correct |
19 ms |
14584 KB |
Output is correct |
15 |
Correct |
19 ms |
14584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14456 KB |
Output is correct |
2 |
Correct |
18 ms |
14584 KB |
Output is correct |
3 |
Correct |
18 ms |
14556 KB |
Output is correct |
4 |
Correct |
14 ms |
14432 KB |
Output is correct |
5 |
Correct |
18 ms |
14584 KB |
Output is correct |
6 |
Correct |
18 ms |
14584 KB |
Output is correct |
7 |
Correct |
15 ms |
14456 KB |
Output is correct |
8 |
Correct |
15 ms |
14460 KB |
Output is correct |
9 |
Correct |
19 ms |
14584 KB |
Output is correct |
10 |
Correct |
19 ms |
14584 KB |
Output is correct |
11 |
Correct |
19 ms |
14588 KB |
Output is correct |
12 |
Correct |
18 ms |
14584 KB |
Output is correct |
13 |
Correct |
19 ms |
14584 KB |
Output is correct |
14 |
Correct |
19 ms |
14584 KB |
Output is correct |
15 |
Correct |
19 ms |
14584 KB |
Output is correct |
16 |
Correct |
559 ms |
27544 KB |
Output is correct |
17 |
Correct |
1049 ms |
43344 KB |
Output is correct |
18 |
Correct |
89 ms |
17580 KB |
Output is correct |
19 |
Correct |
482 ms |
29788 KB |
Output is correct |
20 |
Correct |
1038 ms |
42984 KB |
Output is correct |
21 |
Correct |
673 ms |
32460 KB |
Output is correct |
22 |
Correct |
480 ms |
27792 KB |
Output is correct |
23 |
Correct |
1014 ms |
42716 KB |
Output is correct |
24 |
Correct |
1026 ms |
43020 KB |
Output is correct |
25 |
Correct |
1043 ms |
43128 KB |
Output is correct |
26 |
Correct |
477 ms |
30024 KB |
Output is correct |
27 |
Correct |
480 ms |
30160 KB |
Output is correct |
28 |
Correct |
479 ms |
30140 KB |
Output is correct |
29 |
Correct |
476 ms |
30096 KB |
Output is correct |
30 |
Correct |
496 ms |
30284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
14460 KB |
Output is correct |
2 |
Correct |
15 ms |
14456 KB |
Output is correct |
3 |
Correct |
15 ms |
14456 KB |
Output is correct |
4 |
Correct |
15 ms |
14456 KB |
Output is correct |
5 |
Correct |
15 ms |
14456 KB |
Output is correct |
6 |
Correct |
16 ms |
14456 KB |
Output is correct |
7 |
Correct |
15 ms |
14428 KB |
Output is correct |
8 |
Correct |
15 ms |
14452 KB |
Output is correct |
9 |
Correct |
16 ms |
14452 KB |
Output is correct |
10 |
Correct |
16 ms |
14460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
361 ms |
31976 KB |
Output is correct |
2 |
Correct |
721 ms |
42440 KB |
Output is correct |
3 |
Correct |
728 ms |
42820 KB |
Output is correct |
4 |
Correct |
182 ms |
28892 KB |
Output is correct |
5 |
Correct |
773 ms |
42688 KB |
Output is correct |
6 |
Correct |
738 ms |
42848 KB |
Output is correct |
7 |
Correct |
712 ms |
42880 KB |
Output is correct |
8 |
Correct |
784 ms |
42932 KB |
Output is correct |
9 |
Correct |
708 ms |
42552 KB |
Output is correct |
10 |
Correct |
758 ms |
41892 KB |
Output is correct |
11 |
Correct |
719 ms |
41932 KB |
Output is correct |
12 |
Correct |
766 ms |
42036 KB |
Output is correct |
13 |
Correct |
719 ms |
41944 KB |
Output is correct |
14 |
Correct |
758 ms |
42072 KB |
Output is correct |
15 |
Correct |
736 ms |
41964 KB |
Output is correct |
16 |
Correct |
753 ms |
41928 KB |
Output is correct |
17 |
Correct |
716 ms |
42324 KB |
Output is correct |
18 |
Correct |
727 ms |
42120 KB |
Output is correct |
19 |
Correct |
160 ms |
26580 KB |
Output is correct |
20 |
Correct |
744 ms |
42176 KB |
Output is correct |
21 |
Correct |
620 ms |
42204 KB |
Output is correct |
22 |
Correct |
168 ms |
30000 KB |
Output is correct |
23 |
Correct |
237 ms |
33308 KB |
Output is correct |
24 |
Correct |
173 ms |
29896 KB |
Output is correct |
25 |
Correct |
182 ms |
30144 KB |
Output is correct |
26 |
Correct |
286 ms |
34780 KB |
Output is correct |
27 |
Correct |
182 ms |
28840 KB |
Output is correct |
28 |
Correct |
171 ms |
30208 KB |
Output is correct |
29 |
Correct |
189 ms |
29040 KB |
Output is correct |
30 |
Correct |
169 ms |
30324 KB |
Output is correct |
31 |
Correct |
181 ms |
28960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14456 KB |
Output is correct |
2 |
Correct |
18 ms |
14584 KB |
Output is correct |
3 |
Correct |
18 ms |
14556 KB |
Output is correct |
4 |
Correct |
14 ms |
14432 KB |
Output is correct |
5 |
Correct |
18 ms |
14584 KB |
Output is correct |
6 |
Correct |
18 ms |
14584 KB |
Output is correct |
7 |
Correct |
15 ms |
14456 KB |
Output is correct |
8 |
Correct |
15 ms |
14460 KB |
Output is correct |
9 |
Correct |
19 ms |
14584 KB |
Output is correct |
10 |
Correct |
19 ms |
14584 KB |
Output is correct |
11 |
Correct |
19 ms |
14588 KB |
Output is correct |
12 |
Correct |
18 ms |
14584 KB |
Output is correct |
13 |
Correct |
19 ms |
14584 KB |
Output is correct |
14 |
Correct |
19 ms |
14584 KB |
Output is correct |
15 |
Correct |
19 ms |
14584 KB |
Output is correct |
16 |
Correct |
559 ms |
27544 KB |
Output is correct |
17 |
Correct |
1049 ms |
43344 KB |
Output is correct |
18 |
Correct |
89 ms |
17580 KB |
Output is correct |
19 |
Correct |
482 ms |
29788 KB |
Output is correct |
20 |
Correct |
1038 ms |
42984 KB |
Output is correct |
21 |
Correct |
673 ms |
32460 KB |
Output is correct |
22 |
Correct |
480 ms |
27792 KB |
Output is correct |
23 |
Correct |
1014 ms |
42716 KB |
Output is correct |
24 |
Correct |
1026 ms |
43020 KB |
Output is correct |
25 |
Correct |
1043 ms |
43128 KB |
Output is correct |
26 |
Correct |
477 ms |
30024 KB |
Output is correct |
27 |
Correct |
480 ms |
30160 KB |
Output is correct |
28 |
Correct |
479 ms |
30140 KB |
Output is correct |
29 |
Correct |
476 ms |
30096 KB |
Output is correct |
30 |
Correct |
496 ms |
30284 KB |
Output is correct |
31 |
Correct |
15 ms |
14460 KB |
Output is correct |
32 |
Correct |
15 ms |
14456 KB |
Output is correct |
33 |
Correct |
15 ms |
14456 KB |
Output is correct |
34 |
Correct |
15 ms |
14456 KB |
Output is correct |
35 |
Correct |
15 ms |
14456 KB |
Output is correct |
36 |
Correct |
16 ms |
14456 KB |
Output is correct |
37 |
Correct |
15 ms |
14428 KB |
Output is correct |
38 |
Correct |
15 ms |
14452 KB |
Output is correct |
39 |
Correct |
16 ms |
14452 KB |
Output is correct |
40 |
Correct |
16 ms |
14460 KB |
Output is correct |
41 |
Correct |
361 ms |
31976 KB |
Output is correct |
42 |
Correct |
721 ms |
42440 KB |
Output is correct |
43 |
Correct |
728 ms |
42820 KB |
Output is correct |
44 |
Correct |
182 ms |
28892 KB |
Output is correct |
45 |
Correct |
773 ms |
42688 KB |
Output is correct |
46 |
Correct |
738 ms |
42848 KB |
Output is correct |
47 |
Correct |
712 ms |
42880 KB |
Output is correct |
48 |
Correct |
784 ms |
42932 KB |
Output is correct |
49 |
Correct |
708 ms |
42552 KB |
Output is correct |
50 |
Correct |
758 ms |
41892 KB |
Output is correct |
51 |
Correct |
719 ms |
41932 KB |
Output is correct |
52 |
Correct |
766 ms |
42036 KB |
Output is correct |
53 |
Correct |
719 ms |
41944 KB |
Output is correct |
54 |
Correct |
758 ms |
42072 KB |
Output is correct |
55 |
Correct |
736 ms |
41964 KB |
Output is correct |
56 |
Correct |
753 ms |
41928 KB |
Output is correct |
57 |
Correct |
716 ms |
42324 KB |
Output is correct |
58 |
Correct |
727 ms |
42120 KB |
Output is correct |
59 |
Correct |
160 ms |
26580 KB |
Output is correct |
60 |
Correct |
744 ms |
42176 KB |
Output is correct |
61 |
Correct |
620 ms |
42204 KB |
Output is correct |
62 |
Correct |
168 ms |
30000 KB |
Output is correct |
63 |
Correct |
237 ms |
33308 KB |
Output is correct |
64 |
Correct |
173 ms |
29896 KB |
Output is correct |
65 |
Correct |
182 ms |
30144 KB |
Output is correct |
66 |
Correct |
286 ms |
34780 KB |
Output is correct |
67 |
Correct |
182 ms |
28840 KB |
Output is correct |
68 |
Correct |
171 ms |
30208 KB |
Output is correct |
69 |
Correct |
189 ms |
29040 KB |
Output is correct |
70 |
Correct |
169 ms |
30324 KB |
Output is correct |
71 |
Correct |
181 ms |
28960 KB |
Output is correct |
72 |
Correct |
685 ms |
33120 KB |
Output is correct |
73 |
Correct |
1039 ms |
43672 KB |
Output is correct |
74 |
Correct |
1058 ms |
43604 KB |
Output is correct |
75 |
Correct |
1048 ms |
45188 KB |
Output is correct |
76 |
Correct |
1069 ms |
45628 KB |
Output is correct |
77 |
Correct |
1057 ms |
45560 KB |
Output is correct |
78 |
Correct |
1045 ms |
45604 KB |
Output is correct |
79 |
Correct |
1018 ms |
45324 KB |
Output is correct |
80 |
Correct |
1006 ms |
44712 KB |
Output is correct |
81 |
Correct |
1022 ms |
45568 KB |
Output is correct |
82 |
Correct |
1028 ms |
44600 KB |
Output is correct |
83 |
Correct |
1041 ms |
44648 KB |
Output is correct |
84 |
Correct |
1059 ms |
44660 KB |
Output is correct |
85 |
Correct |
1037 ms |
45200 KB |
Output is correct |
86 |
Correct |
1039 ms |
45012 KB |
Output is correct |
87 |
Correct |
1026 ms |
44816 KB |
Output is correct |
88 |
Correct |
1010 ms |
45812 KB |
Output is correct |
89 |
Correct |
477 ms |
29140 KB |
Output is correct |
90 |
Correct |
1057 ms |
45504 KB |
Output is correct |
91 |
Correct |
961 ms |
45112 KB |
Output is correct |
92 |
Correct |
487 ms |
30948 KB |
Output is correct |
93 |
Correct |
569 ms |
35512 KB |
Output is correct |
94 |
Correct |
487 ms |
31208 KB |
Output is correct |
95 |
Correct |
484 ms |
30836 KB |
Output is correct |
96 |
Correct |
608 ms |
36320 KB |
Output is correct |
97 |
Correct |
498 ms |
29904 KB |
Output is correct |
98 |
Correct |
483 ms |
30700 KB |
Output is correct |
99 |
Correct |
494 ms |
30200 KB |
Output is correct |
100 |
Correct |
481 ms |
30640 KB |
Output is correct |