Submission #615654

#	Time	Username	Problem	Language	Result	Execution time	Memory
615654		erekle	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	2120 ms	47288 KiB

reconstruction

#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 (stderr)

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 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23