Submission #1208973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208973		Braabebo10	Reconstruction Project (JOI22_reconstruction)	C++20	0 / 100	1 ms	716 KiB

reconstruction

#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

struct DSU {
    ll connected;
    vector<ll> par, sz;
    stack<array<ll, 2> > st;

    DSU(ll n) {
        par = sz = vector<ll>(n + 1, 0);
        for (ll i = 1; i <= n; i++)
            par[i] = i, sz[i] = 1;
        connected = n;
    }

    ll findparent(ll u) {
        if (par[u] == u)return u;
        ll parent = findparent(par[u]);
        //if not rollback, uncomment
        par[u] = parent;
        return parent;
    }

    ll getsize(ll u) {
        return sz[findparent(u)];
    }

    void unite(ll u, ll v) {
        ll par1 = findparent(u), par2 = findparent(v);

        st.push({-1, -1});
        if (par1 == par2)
            return;

        if (sz[par1] > sz[par2])
            swap(par1, par2);

        st.pop();
        st.push({connected, par1});
        connected--;

        sz[par2] += sz[par1];
        par[par1] = par2;
    }

    void rollback() {
        if (st.size()) {
            auto x = st.top();
            st.pop();
            if (x[0] == -1)return;
            connected = x[0];
            par[x[1]] = x[1];
        }
    }

    bool is_connected(ll u, ll v) {
        return findparent(u) == findparent(v);
    }
};

array<ll, 2> getS(vector<pair<ll, ll> > &a, ll x) {
    ll sz = a.size(), l = 0, r = sz - 1, ans = -1;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (a[mid].first > x)r = mid - 1;
        else l = mid + 1, ans = mid;
    }
    if (ans == -1)return {0LL, 0LL};
    return {ans + 1, a[ans].second};
}

int main() {
    baraa
    ll n, m;
    cin >> n >> m;
    vector<array<ll, 3> > edges(m);
    map<ll, vector<array<ll, 2> > > mp;
    for (auto &[w, u, v]: edges) {
        cin >> u >> v >> w;
        mp[w].push_back({u, v});
    }
    sort(all(edges));
    map<ll, vector<pair<ll, ll> > > cost;
    map<ll, ll> index;
    vector<ll> weights, l[m], r[m];
    for (ll i = 0; i < m; i++) {
        weights.push_back(edges[i][0]);
        index[edges[i][0]] = i;
        DSU dsu(n);
        dsu.unite(edges[i][1], edges[i][2]);
        l[i].push_back(i);
        if (i)
            for (ll idx: l[i - 1])
                if (!dsu.is_connected(edges[idx][1], edges[idx][2]))
                    dsu.unite(edges[idx][1], edges[idx][2]), l[i].push_back(idx);
    }
    for (ll i = m - 1; i >= 0; i--) {
        DSU dsu(n);
        dsu.unite(edges[i][1], edges[i][2]);
        r[i].push_back(i);
        if (i + 1 < m)
            for (ll idx: r[i + 1])
                if (!dsu.is_connected(edges[idx][1], edges[idx][2]))
                    dsu.unite(edges[idx][1], edges[idx][2]), r[i].push_back(idx);
    }
    sort(all(weights));
    weights.erase(unique(all(weights)), weights.end());
    auto nxtW = [&](ll x) {
        ll it = (upper_bound(all(edges), array<ll, 3>{x, -1LL, -1LL})) - edges.begin();
        return it - 1;
    };
    ll q;
    cin >> q;
    while (q--) {
        ll x;
        cin >> x;
        ll idx = nxtW(x), res = 0;
        DSU dsu(n);
        vector<ll> cur;
        for (ll j: r[idx])cur.push_back(j);
        if (idx - 1 >= 0)
            for (ll j: l[idx - 1])cur.push_back(j);
        sort(all(cur), [&](ll a, ll b) {
            return abs(edges[a][0] - x) < abs(edges[b][0] - x);
        });
        for (ll j: cur)
            if (!dsu.is_connected(edges[j][1], edges[j][2]))
                dsu.unite(edges[j][1], edges[j][2]), res += abs(edges[j][0] - x);
        cout << res << nl;
    }
    return 0;
}

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