Submission #1232269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232269		Double_Slash	Reconstruction Project (JOI22_reconstruction)	C++20	70 / 100	5087 ms	402112 KiB

reconstruction

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
using pint = pair<int, int>;

int n, m, q, par[501];
bool gone[100001];
vector<pint> adj[501];
vector<int> path, pre[100001], suf[100001];

int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }

bool dfs(int i, int t, int p = 0) {
    adj[i].erase(remove_if(all(adj[i]), [&] (pint &p) { return gone[p.second]; }), adj[i].end());
    if (i == t) return true;
    for (auto [j, k]: adj[i]) {
        if (j == p) continue;
        path.emplace_back(k);
        if (dfs(j, t, i)) return true;
        path.pop_back();
    }
    return false;
}

int main() {
    cin >> n >> m;
    vector<array<int, 3>> edges(m);
    for (auto &[w, a, b]: edges) cin >> a >> b >> w;
    sort(all(edges));
    for (int i = m; i--;) {
        suf[i] = suf[i + 1];
        if (dfs(edges[i][1], edges[i][2])) {
            int j = *max_element(all(path), [&] (int a, int b) { return edges[a][0] < edges[b][0]; });
            gone[j] = true;
            path.clear();
            suf[i].erase(find(all(suf[i]), j));
        };
        adj[edges[i][1]].emplace_back(edges[i][2], i);
        adj[edges[i][2]].emplace_back(edges[i][1], i);
        suf[i].emplace_back(i);
        sort(all(suf[i]), [&] (int a, int b) { return edges[a][0] < edges[b][0]; });
    }
    memset(gone, false, sizeof gone);
    for (int i = 1; i <= n; ++i) adj[i].clear();
    for (int i = 0; i < m; ++i) {
        if (i) pre[i] = pre[i - 1];
        if (dfs(edges[i][1], edges[i][2])) {
            int j = *min_element(all(path), [&] (int a, int b) { return edges[a][0] < edges[b][0]; });
            gone[j] = true;
            path.clear();
            pre[i].erase(find(all(pre[i]), j));
        };
        adj[edges[i][1]].emplace_back(edges[i][2], i);
        adj[edges[i][2]].emplace_back(edges[i][1], i);
        pre[i].emplace_back(i);
        sort(all(pre[i]), [&] (int a, int b) { return edges[a][0] > edges[b][0]; });
    }
    cin >> q;
    for (int i = 0; q--;) {
        int x;
        cin >> x;
        while (i < m and edges[i][0] <= x) ++i;
        vector<int> v;
        if (not i) v = suf[i];
        else if (i == m) v = pre[i - 1];
        else {
            v.resize(pre[i - 1].size() + suf[i].size());
            merge(all(pre[i - 1]), all(suf[i]), v.begin(), [&] (int a, int b) { return abs(edges[a][0] - x) < abs(edges[b][0] - x); });
        }
        memset(par, -1, sizeof par);
        ll ans = 0;
        for (int j: v) {
            auto [w, a, b] = edges[j];
            if ((a = find(a)) == (b = find(b))) continue;
            if (-par[a] > -par[b]) swap(a, b);
            par[b] += par[a];
            par[a] = b;
            ans += abs(w - x);
        }
        cout << ans << '\n';
    }
}

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