Submission #1207997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207997		onbert	Reconstruction Project (JOI22_reconstruction)	C++20	0 / 100	0 ms	324 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct thing {
    int u, v, w;
    bool operator < (const thing &b) const {
        return w < b.w;
    }
};
const int maxn = 505;
int n;
vector<thing> edge;
vector<int> vals;

int dsu[maxn], sz[maxn];
int rt(int u) {
    if (dsu[u] == u) return u;
    else return dsu[u] = rt(dsu[u]);
}
void merge(int u, int v) {
    if (sz[u] > sz[v]) swap(u, v);
    dsu[u] = v;
    sz[v] += sz[u];
}
vector<thing> thing1, thing2;

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m;
    cin >> n >> m;
    edge.resize(m);
    for (auto &[u, v, w]:edge) {
        cin >> u >> v >> w;
        vals.push_back(w);
    }
    sort(edge.begin(), edge.end());
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    int mid = (m-1)/2;
    for (int i=1;i<=n;i++) dsu[i] = i, sz[i] = 1;
    for (int i=mid+1;i<m;i++) {
        auto [u, v, w] = edge[i];
        u = rt(u), v = rt(v);
        if (u != v) {
            merge(u, v);
            thing1.push_back(edge[i]);
        }
    }
    for (int i=1;i<=n;i++) dsu[i] = i, sz[i] = 1;
    for (int i=mid;i>=0;i--) {
        auto [u, v, w] = edge[i];
        u = rt(u), v = rt(v);
        if (u != v) {
            merge(u, v);
            thing2.push_back(edge[i]);
        }
    }

    // for (auto [u, v, w]:edge) cout << u << " " << v << " " << w << endl;
    // cout << endl;

    // for (int i:thing1) cout << i << " " << edge[i].u << " " << edge[i].v << endl;
    // cout << endl;
    // for (int i:thing2) cout << i << " " << edge[i].u << " " << edge[i].v << endl;
    // cout << endl;

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        int pt1 = 0, pt2 = 0;
        int sz1 = thing1.size(), sz2 = thing2.size();
        int cnt = 0, ans = 0;
        for (int i=1;i<=n;i++) dsu[i] = i, sz[i] = 1;
        while (cnt < n-1) {
            if (pt2 >= sz2 || thing1[pt1].w - x < x - thing2[pt2].w) {
                auto [u, v, w] = thing1[pt1];
                u = rt(u), v = rt(v);
                if (u != v) {
                    cnt++;
                    merge(u, v);
                    ans += w - x;
                }
                pt1++;
            } else {
                auto [u, v, w] = thing2[pt2];
                // cout << u << " " << v << endl;
                u = rt(u), v = rt(v);
                // cout << u << " " << v << endl;
                if (u != v) {
                    cnt++;
                    merge(u, v);
                    ans += x - w;
                }
                pt2++;
            }
            // if (x == 6) {
            //     cout << pt1 << " " << pt2 << " " << cnt << endl;
            //     cout << ans << endl;
            // }
        }
        cout << ans << "\n";
    }
}

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