oj.uz

Submission #615654

# Submission time Handle Problem Language Result Execution time Memory
615654 2022-07-31T11:38:17 Z erekle Reconstruction Project (JOI22_reconstruction) C++17
100 / 100
 2120 ms 47288 KB 
#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;
      |            ~~^~~~~~~~~~

Subtask #1
3.0 / 3.0

# 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

Subtask #2
4.0 / 4.0

# 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

Subtask #3
7.0 / 7.0

# 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

Subtask #4
28.0 / 28.0

# 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

Subtask #5
35.0 / 35.0

# 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

Subtask #6
23.0 / 23.0

# 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