Submission #759056

#	Time	Username	Problem	Language	Result	Execution time	Memory
759056		Lobo	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1160 ms	852836 KiB

reconstruction

#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 550;
const int maxm = 1e5+10;

int n, m, q, cl[maxm], cr[maxm];
vector<int> mstl[maxm], mstr[maxm], gms[maxn];
vector<pair<int,pair<int,int>>> edges;

int dfsmini(int u, int ed, int anti) {
    if(u == ed) return m;
    for(auto i : gms[u]) if(i != anti) {
        int v = edges[i].sc.fr+edges[i].sc.sc-u;
        int ret = dfsmini(v,ed,i);
        if(ret != -1) return min(ret,i);
    }
    return -1;
}

int dfsmaxi(int u, int ed, int anti) {
    if(u == ed) return 0;
    for(auto i : gms[u]) if(i != anti) {
        int v = edges[i].sc.fr+edges[i].sc.sc-u;
        int ret = dfsmaxi(v,ed,i);
        if(ret != -1) return max(ret,i);
    }
    return -1;
}

void solve() {
    cin >> n >> m;

    for(int i = 1; i <= m; i++) {
        int u,v,w; cin >> u >> v >> w;

        edges.pb(mp(w,mp(u,v)));
    }
    sort(all(edges));

    for(int i = 0; i < m; i++) {
        if(i == 0) {
            mstl[i].pb(i);
            gms[edges[i].sc.fr].pb(i);
            gms[edges[i].sc.sc].pb(i);
            cl[i] = 0;
        }
        else {
            mstl[i] = mstl[i-1];
            int ui = edges[i].sc.fr;
            int vi = edges[i].sc.sc;

            int j = dfsmini(ui,vi,-1);
            
            if(j == -1) {
                mstl[i].pb(i);
                gms[edges[i].sc.fr].pb(i);
                gms[edges[i].sc.sc].pb(i);
                cl[i] = 0;
            }
            else {
                cl[i] = (edges[i].fr+edges[j].fr+1+(2-1))/2;
                auto it1 = find(all(mstl[i]),j);
                mstl[i].erase(it1);
                auto it2 = find(all(gms[edges[j].sc.fr]),j);
                gms[edges[j].sc.fr].erase(it2);
                auto it3 = find(all(gms[edges[j].sc.sc]),j);
                gms[edges[j].sc.sc].erase(it3);

                mstl[i].pb(i);
                gms[ui].pb(i);
                gms[vi].pb(i);
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        gms[i].clear();
    }

    for(int i = m-1; i >= 0; i--) {
        if(i == m-1) {
            mstr[i].pb(i);
            gms[edges[i].sc.fr].pb(i);
            gms[edges[i].sc.sc].pb(i);
            cr[i] = inf;
        }
        else {
            mstr[i] = mstr[i+1];
            int ui = edges[i].sc.fr;
            int vi = edges[i].sc.sc;

            int j = dfsmaxi(ui,vi,-1);
            if(j == -1) {
                mstr[i].pb(i);
                gms[edges[i].sc.fr].pb(i);
                gms[edges[i].sc.sc].pb(i);
                cr[i] = inf;
            }
            else {
                cr[i] = (edges[i].fr+edges[j].fr)/2;

                auto it1 = find(all(mstr[i]),j);
                mstr[i].erase(it1);

                auto it2 = find(all(gms[edges[j].sc.fr]),j);
                gms[edges[j].sc.fr].erase(it2);
                auto it3 = find(all(gms[edges[j].sc.sc]),j);
                gms[edges[j].sc.sc].erase(it3);

                mstr[i].pb(i);
                gms[ui].pb(i);
                gms[vi].pb(i);
            }
        }
    }

    cin >> q;
    vector<pair<int,pair<int,int>>> qrs;
    for(int i = 0; i < q; i++) {
        int c; cin >> c;
        qrs.pb(mp(c,mp(0,i)));
    }
    for(int i = 0; i < m; i++) {
        qrs.pb(mp(cl[i],mp(-1,i)));
        qrs.pb(mp(cr[i],mp(1,i)));
        qrs.pb(mp(edges[i].fr,mp(2,i)));
    }

    sort(all(qrs));

    int ans = 0;
    int qp = 0;
    int qn = 0;
    for(auto X : qrs) {
        if(X.sc.fr == 0) {
            cout << ans+qp*X.fr-qn*X.fr << endl;
        }
        else if(X.sc.fr == -1) {
            qn++;
            ans+= edges[X.sc.sc].fr;
        }
        else if(X.sc.fr == 2) {
            qp++;
            qn--;
            ans-= 2*edges[X.sc.sc].fr;
        }
        else {
            qp--;
            ans+= edges[X.sc.sc].fr;
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

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