#include <bits/stdc++.h>
using namespace std;
vector<pair<int, pair<int, int>>> edges;
vector<vector<pair<int, int>>> g;
int minEdge;
bool dfsMin(int node, int parent, int target, int minE) {
if (node == target) {
minEdge = minE;
return true;
}
for (auto [child, e] : g[node]) {
if (child == parent) continue;
int newMinE = min(minE, e); // since indexed by weight, can simply take minimum
if (dfsMin(child, node, target, newMinE)) return true;
}
return false;
}
void removeEdge(vector<pair<int, int>> &v, int e) {
int i = 0;
while (i < v.size() && v[i].second != e) ++i;
if (i < (int)v.size()) v.erase(v.begin()+i);
}
const int INF = 1e9 + 1;
int main() {
int n, m; cin >> n >> m;
edges.resize(m);
for (auto &[w, p] : edges) cin >> p.first >> p.second >> w;
sort(edges.begin(), edges.end());
vector<int> first(m), last(m, INF-1);
g.resize(1+n);
for (int i = 0; i < m; ++i) {
auto [w, p] = edges[i];
auto [a, b] = p;
minEdge = INF;
if (dfsMin(a, -1, b, INF)) {
first[i] = (w + edges[minEdge].first + 1) / 2;
last[minEdge] = first[i]-1;
auto [c, d] = edges[minEdge].second;
removeEdge(g[c], minEdge);
removeEdge(g[d], minEdge);
} else first[i] = 1;
g[a].emplace_back(b, i);
g[b].emplace_back(a, i);
}
int q; cin >> q;
vector<int> x(1+q+1);
for (int i = 1; i <= q; ++i) cin >> x[i];
x[0] = 0, x[q+1] = INF;
auto findNext = [&x](int i) {
return lower_bound(x.begin(), x.end(), i) - x.begin();
};
vector<long long> k(1+q+1), b(1+q+1); // minCost: kx + b
auto addRange = [&k, &b](int l, int r, int dk, int db) {
k[l] += dk, b[l] += db;
k[r] -= dk, b[r] -= db;
};
for (int i = 0; i < m; ++i) {
int w = edges[i].first;
int f = findNext(first[i]), l = findNext(last[i]+1); // [f, l)
int mid = findNext(w);
addRange(f, mid, -1, w); // in range [f, mid) we add w-x
addRange(mid, l, 1, -w); // in range [mid, l) we add x-w
}
for (int i = 1; i <= q; ++i) {
k[i] += k[i-1];
b[i] += b[i-1];
cout << k[i] * x[i] + b[i] << endl;
}
return 0;
}
Compilation message
reconstruction.cpp: In function 'void removeEdge(std::vector<std::pair<int, int> >&, int)':
reconstruction.cpp:22:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | while (i < v.size() && v[i].second != e) ++i;
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
304 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
304 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
443 ms |
3988 KB |
Output is correct |
21 |
Correct |
252 ms |
4012 KB |
Output is correct |
22 |
Correct |
398 ms |
4008 KB |
Output is correct |
23 |
Correct |
388 ms |
4016 KB |
Output is correct |
24 |
Correct |
377 ms |
4008 KB |
Output is correct |
25 |
Correct |
435 ms |
4024 KB |
Output is correct |
26 |
Correct |
439 ms |
4016 KB |
Output is correct |
27 |
Correct |
447 ms |
4008 KB |
Output is correct |
28 |
Correct |
424 ms |
4008 KB |
Output is correct |
29 |
Correct |
297 ms |
4152 KB |
Output is correct |
30 |
Correct |
455 ms |
4020 KB |
Output is correct |
31 |
Correct |
427 ms |
3980 KB |
Output is correct |
32 |
Correct |
414 ms |
3996 KB |
Output is correct |
33 |
Correct |
423 ms |
4020 KB |
Output is correct |
34 |
Correct |
218 ms |
5096 KB |
Output is correct |
35 |
Correct |
390 ms |
4016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1823 ms |
44236 KB |
Output is correct |
5 |
Correct |
1813 ms |
44248 KB |
Output is correct |
6 |
Correct |
1872 ms |
44176 KB |
Output is correct |
7 |
Correct |
1670 ms |
46176 KB |
Output is correct |
8 |
Correct |
1706 ms |
46428 KB |
Output is correct |
9 |
Correct |
1669 ms |
46424 KB |
Output is correct |
10 |
Correct |
1786 ms |
44404 KB |
Output is correct |
11 |
Correct |
1679 ms |
46408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
304 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1604 ms |
41764 KB |
Output is correct |
21 |
Correct |
1588 ms |
42040 KB |
Output is correct |
22 |
Correct |
1584 ms |
41936 KB |
Output is correct |
23 |
Correct |
1564 ms |
41904 KB |
Output is correct |
24 |
Correct |
1517 ms |
41900 KB |
Output is correct |
25 |
Correct |
1541 ms |
41948 KB |
Output is correct |
26 |
Correct |
1534 ms |
41804 KB |
Output is correct |
27 |
Correct |
1519 ms |
41896 KB |
Output is correct |
28 |
Correct |
1546 ms |
41760 KB |
Output is correct |
29 |
Correct |
1520 ms |
41772 KB |
Output is correct |
30 |
Correct |
1561 ms |
41852 KB |
Output is correct |
31 |
Correct |
1572 ms |
41932 KB |
Output is correct |
32 |
Correct |
1527 ms |
42308 KB |
Output is correct |
33 |
Correct |
1558 ms |
41700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
304 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
443 ms |
3988 KB |
Output is correct |
21 |
Correct |
252 ms |
4012 KB |
Output is correct |
22 |
Correct |
398 ms |
4008 KB |
Output is correct |
23 |
Correct |
388 ms |
4016 KB |
Output is correct |
24 |
Correct |
377 ms |
4008 KB |
Output is correct |
25 |
Correct |
435 ms |
4024 KB |
Output is correct |
26 |
Correct |
439 ms |
4016 KB |
Output is correct |
27 |
Correct |
447 ms |
4008 KB |
Output is correct |
28 |
Correct |
424 ms |
4008 KB |
Output is correct |
29 |
Correct |
297 ms |
4152 KB |
Output is correct |
30 |
Correct |
455 ms |
4020 KB |
Output is correct |
31 |
Correct |
427 ms |
3980 KB |
Output is correct |
32 |
Correct |
414 ms |
3996 KB |
Output is correct |
33 |
Correct |
423 ms |
4020 KB |
Output is correct |
34 |
Correct |
218 ms |
5096 KB |
Output is correct |
35 |
Correct |
390 ms |
4016 KB |
Output is correct |
36 |
Correct |
419 ms |
4868 KB |
Output is correct |
37 |
Correct |
270 ms |
4784 KB |
Output is correct |
38 |
Correct |
371 ms |
4772 KB |
Output is correct |
39 |
Correct |
384 ms |
4724 KB |
Output is correct |
40 |
Correct |
369 ms |
4776 KB |
Output is correct |
41 |
Correct |
432 ms |
4800 KB |
Output is correct |
42 |
Correct |
420 ms |
4752 KB |
Output is correct |
43 |
Correct |
433 ms |
4772 KB |
Output is correct |
44 |
Correct |
425 ms |
4728 KB |
Output is correct |
45 |
Correct |
309 ms |
5164 KB |
Output is correct |
46 |
Correct |
416 ms |
4732 KB |
Output is correct |
47 |
Correct |
457 ms |
4756 KB |
Output is correct |
48 |
Correct |
423 ms |
4840 KB |
Output is correct |
49 |
Correct |
423 ms |
4724 KB |
Output is correct |
50 |
Correct |
243 ms |
5984 KB |
Output is correct |
51 |
Correct |
415 ms |
4892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
304 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
300 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
443 ms |
3988 KB |
Output is correct |
21 |
Correct |
252 ms |
4012 KB |
Output is correct |
22 |
Correct |
398 ms |
4008 KB |
Output is correct |
23 |
Correct |
388 ms |
4016 KB |
Output is correct |
24 |
Correct |
377 ms |
4008 KB |
Output is correct |
25 |
Correct |
435 ms |
4024 KB |
Output is correct |
26 |
Correct |
439 ms |
4016 KB |
Output is correct |
27 |
Correct |
447 ms |
4008 KB |
Output is correct |
28 |
Correct |
424 ms |
4008 KB |
Output is correct |
29 |
Correct |
297 ms |
4152 KB |
Output is correct |
30 |
Correct |
455 ms |
4020 KB |
Output is correct |
31 |
Correct |
427 ms |
3980 KB |
Output is correct |
32 |
Correct |
414 ms |
3996 KB |
Output is correct |
33 |
Correct |
423 ms |
4020 KB |
Output is correct |
34 |
Correct |
218 ms |
5096 KB |
Output is correct |
35 |
Correct |
390 ms |
4016 KB |
Output is correct |
36 |
Correct |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
1 ms |
212 KB |
Output is correct |
39 |
Correct |
1823 ms |
44236 KB |
Output is correct |
40 |
Correct |
1813 ms |
44248 KB |
Output is correct |
41 |
Correct |
1872 ms |
44176 KB |
Output is correct |
42 |
Correct |
1670 ms |
46176 KB |
Output is correct |
43 |
Correct |
1706 ms |
46428 KB |
Output is correct |
44 |
Correct |
1669 ms |
46424 KB |
Output is correct |
45 |
Correct |
1786 ms |
44404 KB |
Output is correct |
46 |
Correct |
1679 ms |
46408 KB |
Output is correct |
47 |
Correct |
1 ms |
212 KB |
Output is correct |
48 |
Correct |
1604 ms |
41764 KB |
Output is correct |
49 |
Correct |
1588 ms |
42040 KB |
Output is correct |
50 |
Correct |
1584 ms |
41936 KB |
Output is correct |
51 |
Correct |
1564 ms |
41904 KB |
Output is correct |
52 |
Correct |
1517 ms |
41900 KB |
Output is correct |
53 |
Correct |
1541 ms |
41948 KB |
Output is correct |
54 |
Correct |
1534 ms |
41804 KB |
Output is correct |
55 |
Correct |
1519 ms |
41896 KB |
Output is correct |
56 |
Correct |
1546 ms |
41760 KB |
Output is correct |
57 |
Correct |
1520 ms |
41772 KB |
Output is correct |
58 |
Correct |
1561 ms |
41852 KB |
Output is correct |
59 |
Correct |
1572 ms |
41932 KB |
Output is correct |
60 |
Correct |
1527 ms |
42308 KB |
Output is correct |
61 |
Correct |
1558 ms |
41700 KB |
Output is correct |
62 |
Correct |
419 ms |
4868 KB |
Output is correct |
63 |
Correct |
270 ms |
4784 KB |
Output is correct |
64 |
Correct |
371 ms |
4772 KB |
Output is correct |
65 |
Correct |
384 ms |
4724 KB |
Output is correct |
66 |
Correct |
369 ms |
4776 KB |
Output is correct |
67 |
Correct |
432 ms |
4800 KB |
Output is correct |
68 |
Correct |
420 ms |
4752 KB |
Output is correct |
69 |
Correct |
433 ms |
4772 KB |
Output is correct |
70 |
Correct |
425 ms |
4728 KB |
Output is correct |
71 |
Correct |
309 ms |
5164 KB |
Output is correct |
72 |
Correct |
416 ms |
4732 KB |
Output is correct |
73 |
Correct |
457 ms |
4756 KB |
Output is correct |
74 |
Correct |
423 ms |
4840 KB |
Output is correct |
75 |
Correct |
423 ms |
4724 KB |
Output is correct |
76 |
Correct |
243 ms |
5984 KB |
Output is correct |
77 |
Correct |
415 ms |
4892 KB |
Output is correct |
78 |
Correct |
2120 ms |
43332 KB |
Output is correct |
79 |
Correct |
1780 ms |
45416 KB |
Output is correct |
80 |
Correct |
1904 ms |
44284 KB |
Output is correct |
81 |
Correct |
1943 ms |
44296 KB |
Output is correct |
82 |
Correct |
1906 ms |
43388 KB |
Output is correct |
83 |
Correct |
1966 ms |
43300 KB |
Output is correct |
84 |
Correct |
1963 ms |
43316 KB |
Output is correct |
85 |
Correct |
1956 ms |
43304 KB |
Output is correct |
86 |
Correct |
1976 ms |
43212 KB |
Output is correct |
87 |
Correct |
1791 ms |
45016 KB |
Output is correct |
88 |
Correct |
1908 ms |
43252 KB |
Output is correct |
89 |
Correct |
1939 ms |
43304 KB |
Output is correct |
90 |
Correct |
1906 ms |
43356 KB |
Output is correct |
91 |
Correct |
1906 ms |
43140 KB |
Output is correct |
92 |
Correct |
1747 ms |
47288 KB |
Output is correct |
93 |
Correct |
1926 ms |
44368 KB |
Output is correct |