#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int INF = 1e9 + 1;
const int SIZE = 505;
const int MSIZ = 1e5 + 5;
int n, m, q;
int to[SIZE], h[SIZE];
int l[MSIZ], r[MSIZ];
int pa[SIZE], pid[SIZE], dep[SIZE];
tuple<int, int, int> e[MSIZ];
vector<pair<int, int>> adj[SIZE];
vector<pair<int, int>> dcnt, dsum;
int dsu(int x) {
return x == to[x] ? x : (to[x] = dsu(to[x]));
}
bool Merge(int a, int b) {
a = dsu(a), b = dsu(b);
if (a == b) return 0;
if (h[a] < h[b]) swap(a, b);
to[b] = a;
h[a] += h[a] == h[b];
return 1;
}
void solve() {
cin >> n >> m;
FOR (i, 1, m) {
auto &[w, a, b] = e[i];
cin >> a >> b >> w;
}
sort(e + 1, e + m + 1);
iota(to + 1, to + n + 1, 1);
auto dfs = [&](auto dfs, int pos)->void {
for (auto [np, id] : adj[pos]) if (np != pa[pos]) {
pa[np] = pos;
pid[np] = id;
dep[np] = dep[pos] + 1;
dfs(dfs, np);
}
};
auto build = [&]() {
fill(pa + 1, pa + n + 1, 0);
FOR (i, 1, n) if (!pa[i]) {
pid[i] = 0;
dep[i] = 1;
dfs(dfs, i);
}
};
FOR (i, 1, m) {
build();
auto [w, a, b] = e[i];
if (Merge(a, b)) {
adj[a].pb(b, i);
adj[b].pb(a, i);
r[i] = INF;
continue;
}
int mn = INF, id;
for (int ca = a, cb = b; ca != cb; ca = pa[ca]) {
if (dep[ca] < dep[cb]) swap(ca, cb);
if (get<0>(e[pid[ca]]) < mn) {
mn = get<0>(e[pid[ca]]);
id = pid[ca];
}
}
l[i] = (w + mn + 1) / 2;
r[id] = l[i] - 1;
r[i] = INF;
int ca, cb;
tie(w, ca, cb) = e[id];
adj[ca].erase(find(adj[ca].begin(), adj[ca].end(), make_pair(cb, id)));
adj[cb].erase(find(adj[cb].begin(), adj[cb].end(), make_pair(ca, id)));
adj[a].pb(b, i);
adj[b].pb(a, i);
}
FOR (i, 1, m) {
auto [w, a, b] = e[i];
if (r[i] <= w) {
dcnt.pb(l[i], -1), dcnt.pb(r[i] + 1, 1);
dsum.pb(l[i], w), dsum.pb(r[i] + 1, -w);
} else if (l[i] >= w) {
dcnt.pb(l[i], 1), dcnt.pb(r[i] + 1, -1);
dsum.pb(l[i], -w), dsum.pb(r[i] + 1, w);
} else {
dcnt.pb(l[i], -1), dcnt.pb(w + 1, 1);
dsum.pb(l[i], w), dsum.pb(w + 1, -w);
dcnt.pb(w + 1, 1), dcnt.pb(r[i] + 1, -1);
dsum.pb(w + 1, -w), dsum.pb(r[i] + 1, w);
}
}
sort(dcnt.begin(), dcnt.end());
sort(dsum.begin(), dsum.end());
int cnt = 0;
ll sum = 0;
cin >> q;
int p = 0;
while (q--) {
int x;
cin >> x;
while (p < dcnt.size() && dcnt[p].F <= x) {
cnt += dcnt[p].S;
sum += dsum[p].S;
p++;
}
cout << sum + 1ll * cnt * x << '\n';
}
}
int main() {
Waimai;
solve();
}
Compilation message
reconstruction.cpp: In function 'void solve()':
reconstruction.cpp:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | while (p < dcnt.size() && dcnt[p].F <= x) {
| ~~^~~~~~~~~~~~~
reconstruction.cpp:81:23: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
81 | int mn = INF, id;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
336 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
336 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
849 ms |
10468 KB |
Output is correct |
21 |
Correct |
718 ms |
10460 KB |
Output is correct |
22 |
Correct |
757 ms |
10452 KB |
Output is correct |
23 |
Correct |
767 ms |
10472 KB |
Output is correct |
24 |
Correct |
800 ms |
10448 KB |
Output is correct |
25 |
Correct |
835 ms |
10396 KB |
Output is correct |
26 |
Correct |
850 ms |
10404 KB |
Output is correct |
27 |
Correct |
832 ms |
10592 KB |
Output is correct |
28 |
Correct |
796 ms |
10580 KB |
Output is correct |
29 |
Correct |
591 ms |
7472 KB |
Output is correct |
30 |
Correct |
841 ms |
10436 KB |
Output is correct |
31 |
Correct |
827 ms |
10472 KB |
Output is correct |
32 |
Correct |
828 ms |
10500 KB |
Output is correct |
33 |
Correct |
828 ms |
10556 KB |
Output is correct |
34 |
Correct |
485 ms |
7676 KB |
Output is correct |
35 |
Correct |
826 ms |
10464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
908 ms |
31268 KB |
Output is correct |
5 |
Correct |
894 ms |
31232 KB |
Output is correct |
6 |
Correct |
923 ms |
31208 KB |
Output is correct |
7 |
Correct |
612 ms |
33124 KB |
Output is correct |
8 |
Correct |
579 ms |
33200 KB |
Output is correct |
9 |
Correct |
583 ms |
33204 KB |
Output is correct |
10 |
Correct |
888 ms |
31292 KB |
Output is correct |
11 |
Correct |
571 ms |
33476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
336 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
201 ms |
22320 KB |
Output is correct |
21 |
Correct |
199 ms |
22604 KB |
Output is correct |
22 |
Correct |
202 ms |
22440 KB |
Output is correct |
23 |
Correct |
207 ms |
22476 KB |
Output is correct |
24 |
Correct |
206 ms |
22440 KB |
Output is correct |
25 |
Correct |
199 ms |
22348 KB |
Output is correct |
26 |
Correct |
198 ms |
22428 KB |
Output is correct |
27 |
Correct |
200 ms |
22464 KB |
Output is correct |
28 |
Correct |
198 ms |
22360 KB |
Output is correct |
29 |
Correct |
194 ms |
22424 KB |
Output is correct |
30 |
Correct |
202 ms |
22520 KB |
Output is correct |
31 |
Correct |
204 ms |
22356 KB |
Output is correct |
32 |
Correct |
208 ms |
23004 KB |
Output is correct |
33 |
Correct |
225 ms |
22268 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
336 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
849 ms |
10468 KB |
Output is correct |
21 |
Correct |
718 ms |
10460 KB |
Output is correct |
22 |
Correct |
757 ms |
10452 KB |
Output is correct |
23 |
Correct |
767 ms |
10472 KB |
Output is correct |
24 |
Correct |
800 ms |
10448 KB |
Output is correct |
25 |
Correct |
835 ms |
10396 KB |
Output is correct |
26 |
Correct |
850 ms |
10404 KB |
Output is correct |
27 |
Correct |
832 ms |
10592 KB |
Output is correct |
28 |
Correct |
796 ms |
10580 KB |
Output is correct |
29 |
Correct |
591 ms |
7472 KB |
Output is correct |
30 |
Correct |
841 ms |
10436 KB |
Output is correct |
31 |
Correct |
827 ms |
10472 KB |
Output is correct |
32 |
Correct |
828 ms |
10500 KB |
Output is correct |
33 |
Correct |
828 ms |
10556 KB |
Output is correct |
34 |
Correct |
485 ms |
7676 KB |
Output is correct |
35 |
Correct |
826 ms |
10464 KB |
Output is correct |
36 |
Correct |
849 ms |
10768 KB |
Output is correct |
37 |
Correct |
712 ms |
10928 KB |
Output is correct |
38 |
Correct |
746 ms |
10912 KB |
Output is correct |
39 |
Correct |
770 ms |
10824 KB |
Output is correct |
40 |
Correct |
811 ms |
10884 KB |
Output is correct |
41 |
Correct |
838 ms |
10796 KB |
Output is correct |
42 |
Correct |
861 ms |
10840 KB |
Output is correct |
43 |
Correct |
853 ms |
10956 KB |
Output is correct |
44 |
Correct |
795 ms |
10836 KB |
Output is correct |
45 |
Correct |
602 ms |
7984 KB |
Output is correct |
46 |
Correct |
853 ms |
10920 KB |
Output is correct |
47 |
Correct |
831 ms |
10916 KB |
Output is correct |
48 |
Correct |
842 ms |
10864 KB |
Output is correct |
49 |
Correct |
855 ms |
11100 KB |
Output is correct |
50 |
Correct |
503 ms |
8112 KB |
Output is correct |
51 |
Correct |
859 ms |
10908 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
336 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
849 ms |
10468 KB |
Output is correct |
21 |
Correct |
718 ms |
10460 KB |
Output is correct |
22 |
Correct |
757 ms |
10452 KB |
Output is correct |
23 |
Correct |
767 ms |
10472 KB |
Output is correct |
24 |
Correct |
800 ms |
10448 KB |
Output is correct |
25 |
Correct |
835 ms |
10396 KB |
Output is correct |
26 |
Correct |
850 ms |
10404 KB |
Output is correct |
27 |
Correct |
832 ms |
10592 KB |
Output is correct |
28 |
Correct |
796 ms |
10580 KB |
Output is correct |
29 |
Correct |
591 ms |
7472 KB |
Output is correct |
30 |
Correct |
841 ms |
10436 KB |
Output is correct |
31 |
Correct |
827 ms |
10472 KB |
Output is correct |
32 |
Correct |
828 ms |
10500 KB |
Output is correct |
33 |
Correct |
828 ms |
10556 KB |
Output is correct |
34 |
Correct |
485 ms |
7676 KB |
Output is correct |
35 |
Correct |
826 ms |
10464 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
340 KB |
Output is correct |
38 |
Correct |
1 ms |
340 KB |
Output is correct |
39 |
Correct |
908 ms |
31268 KB |
Output is correct |
40 |
Correct |
894 ms |
31232 KB |
Output is correct |
41 |
Correct |
923 ms |
31208 KB |
Output is correct |
42 |
Correct |
612 ms |
33124 KB |
Output is correct |
43 |
Correct |
579 ms |
33200 KB |
Output is correct |
44 |
Correct |
583 ms |
33204 KB |
Output is correct |
45 |
Correct |
888 ms |
31292 KB |
Output is correct |
46 |
Correct |
571 ms |
33476 KB |
Output is correct |
47 |
Correct |
1 ms |
340 KB |
Output is correct |
48 |
Correct |
201 ms |
22320 KB |
Output is correct |
49 |
Correct |
199 ms |
22604 KB |
Output is correct |
50 |
Correct |
202 ms |
22440 KB |
Output is correct |
51 |
Correct |
207 ms |
22476 KB |
Output is correct |
52 |
Correct |
206 ms |
22440 KB |
Output is correct |
53 |
Correct |
199 ms |
22348 KB |
Output is correct |
54 |
Correct |
198 ms |
22428 KB |
Output is correct |
55 |
Correct |
200 ms |
22464 KB |
Output is correct |
56 |
Correct |
198 ms |
22360 KB |
Output is correct |
57 |
Correct |
194 ms |
22424 KB |
Output is correct |
58 |
Correct |
202 ms |
22520 KB |
Output is correct |
59 |
Correct |
204 ms |
22356 KB |
Output is correct |
60 |
Correct |
208 ms |
23004 KB |
Output is correct |
61 |
Correct |
225 ms |
22268 KB |
Output is correct |
62 |
Correct |
849 ms |
10768 KB |
Output is correct |
63 |
Correct |
712 ms |
10928 KB |
Output is correct |
64 |
Correct |
746 ms |
10912 KB |
Output is correct |
65 |
Correct |
770 ms |
10824 KB |
Output is correct |
66 |
Correct |
811 ms |
10884 KB |
Output is correct |
67 |
Correct |
838 ms |
10796 KB |
Output is correct |
68 |
Correct |
861 ms |
10840 KB |
Output is correct |
69 |
Correct |
853 ms |
10956 KB |
Output is correct |
70 |
Correct |
795 ms |
10836 KB |
Output is correct |
71 |
Correct |
602 ms |
7984 KB |
Output is correct |
72 |
Correct |
853 ms |
10920 KB |
Output is correct |
73 |
Correct |
831 ms |
10916 KB |
Output is correct |
74 |
Correct |
842 ms |
10864 KB |
Output is correct |
75 |
Correct |
855 ms |
11100 KB |
Output is correct |
76 |
Correct |
503 ms |
8112 KB |
Output is correct |
77 |
Correct |
859 ms |
10908 KB |
Output is correct |
78 |
Correct |
1037 ms |
30224 KB |
Output is correct |
79 |
Correct |
904 ms |
32316 KB |
Output is correct |
80 |
Correct |
924 ms |
31336 KB |
Output is correct |
81 |
Correct |
950 ms |
31344 KB |
Output is correct |
82 |
Correct |
987 ms |
30416 KB |
Output is correct |
83 |
Correct |
1004 ms |
30376 KB |
Output is correct |
84 |
Correct |
1012 ms |
30392 KB |
Output is correct |
85 |
Correct |
1033 ms |
30300 KB |
Output is correct |
86 |
Correct |
1006 ms |
30144 KB |
Output is correct |
87 |
Correct |
790 ms |
28912 KB |
Output is correct |
88 |
Correct |
1020 ms |
30184 KB |
Output is correct |
89 |
Correct |
1022 ms |
30288 KB |
Output is correct |
90 |
Correct |
1014 ms |
30444 KB |
Output is correct |
91 |
Correct |
1018 ms |
30096 KB |
Output is correct |
92 |
Correct |
688 ms |
30120 KB |
Output is correct |
93 |
Correct |
1024 ms |
31384 KB |
Output is correct |