Submission #812612

#	Time	Username	Problem	Language	Result	Execution time	Memory
812612		hugo_pm	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1080 ms	30396 KiB

reconstruction

#include <bits/stdc++.h>
#define int long long
using namespace std;
    
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define sz(v) ((int)((v).size()))
    
template<typename T>
void chmax(T &x, const T &v) { if (x < v) x = v; }
template<typename T>
void chmin(T &x, const T &v) { if (x > v) x = v; }
    
using pii = pair<int, int>;
using vi = vector<int>;

struct Edge {
    int u, v, p;
};
int nbNode, nbEdge, nbReq;
vector<Edge> edges;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> nbNode >> nbEdge;
    edges.resize(nbEdge);
    for (auto &[u,v,p] : edges) {
        cin >> u >> v >> p;
        --u, --v;
        p *= 2;
    }
    auto compZero = [&] (Edge a, Edge b) { return a.p < b.p; };
    sort(all(edges), compZero);
    
    vector<vi> adjTree(nbNode);
    auto add = [&] (int iEdge) {
        const auto [u,v,_] = edges[iEdge];
        adjTree[u].push_back(iEdge);
        adjTree[v].push_back(iEdge);
    };
    auto remove = [&] (int iEdge) {
        const auto [u,v,_] = edges[iEdge];
        for (int c : {u, v})
            adjTree[c].erase(find(all(adjTree[c]), iEdge));
    };
    auto Dfs = [&] (auto dfs, int node, int parent, int dest, pii &ans) -> bool {
        if (node == dest) {
            return true;
        }
        for (int iEdge : adjTree[node]) {
            const auto [u,v,p] = edges[iEdge];
            int child = u^v^node;
            if (child == parent) continue;
            if(dfs(dfs, child, node, dest, ans)) {
                chmin(ans, make_pair(p, iEdge));
                return true;
            }
        }
        return false;
    };

    vector<pii> events;
    int realAdds = 0;
    rep(iCur, 0, nbEdge) {
        auto &cur = edges[iCur];
        pii ret {1e18, 0};
        if (Dfs(Dfs, cur.u, -1, cur.v, ret)) {
            auto [minTime, argMin] = ret;
            int betterTime = (cur.p + minTime)/2;
            remove(argMin);
            add(iCur);
            events.emplace_back(betterTime, minTime);
            events.emplace_back(betterTime, -cur.p);
        } else if (realAdds < nbNode-1) {
            ++realAdds;
            add(iCur);
            events.emplace_back(0, -cur.p);
        }
    }

    sort(all(events));
    cin >> nbReq;
    vector<int> curMst;
    int ptr = 0;
    rep(iReq, 0, nbReq) {
        int X; cin >> X; X *= 2;
        while (ptr < sz(events) && events[ptr].first <= X) {
            int u = events[ptr].second;
            if (u < 0)
                curMst.push_back(-u);
            else
                curMst.erase(find(all(curMst), u)); 
            ++ptr;
        }
        int ans = 0;
        for (int p : curMst) {
            ans += abs(p-X);
        }
        cout << ans/2 << '\n';
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23