Submission #1208957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208957		Braabebo10	Reconstruction Project (JOI22_reconstruction)	C++20	0 / 100	5103 ms	219440 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> valid;
    vector<ll> weights;
    for (auto [cur, vec]: mp) {
        DSU dsu(n);
        weights.push_back(cur);
        ll prf = 0;
        for (auto [w, u, v]: edges) {
            if (w >= cur and !dsu.is_connected(u, v))
                dsu.unite(u, v), prf += w, cost[cur].push_back({w, prf});
        }
        valid[cur] = dsu.connected == 1;
    }
    auto nxtW = [&](ll x) {
        ll it = (upper_bound(all(weights), x)) - weights.begin();
        if (it == weights.size() or (it > 0 and weights[it - 1] == x))it--;
        // cout << x << ' ' << weights[it] << nl;
        return weights[it];
    };
    ll q;
    cin >> q;
    while (q--) {
        ll x;
        cin >> x;
        ll l = 0, r = 2e9 + 1, ans = 0;
        while (l <= r) {
            ll mid = (l + r) / 2, st = max(1LL, x - mid), ed = x + mid;
            // cout << mid << nl;
            if (!valid[nxtW(st)] or cost[nxtW(st)].back().first > ed)l = mid + 1;
            else r = mid - 1, ans = mid;
        }
        ll st = max(1LL, x - ans), ed = x + ans, res = 0;
        auto [cnt, sm] = getS(cost[nxtW(st)], x);
        res += cnt * x - sm;
        cnt = cost[nxtW(st)].size() - cnt;
        sm = cost[nxtW(st)].back().second - sm;
        res += sm - cnt * 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