Submission #1150939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150939		Math4Life2020	Bridges (APIO19_bridges)	C++20	100 / 100	2853 ms	34704 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;

ll N,M;
const ll Nm = 5e4+5;
vector<array<ll,3>> edg; //{u,v,d}
vector<array<ll,3>> upd0;

//DSU with simple rollback
vector<ll> f[Nm];
vector<ll> sz[Nm];
vector<ll> rbk; //positive -> f, negative -> sz

ll gt(ll x) {
    if (f[x].back()==x) {
        return x;
    } else {
        return gt(f[x].back());
    }
}

void rollbk() {
    for (ll x: rbk) {
        if (x>0) {
            f[x-1].pop_back();
        } else {
            sz[-x-1].pop_back();
        }
    }
    rbk.clear();
}

void fz(ll a, ll b) {
    a = gt(a); b = gt(b);
    if (a==b) {
        return;
    }
    if (sz[a].back()>sz[b].back()) {
        swap(a,b);
    }
    sz[b].push_back(sz[a].back()+sz[b].back());
    rbk.push_back(-1-b);
    f[a].push_back(b);
    rbk.push_back(1+a);
}

void UPD(vector<array<ll,3>> upd) {
    ll K = upd.size();
    vector<ll> ans(K,-1);
    rbk.clear();
    for (ll i=0;i<Nm;i++) {
        f[i].clear();
        sz[i].clear();
        f[i].push_back(i);
        sz[i].push_back(1);
    }
    ll tupd[M];
    for (ll m=0;m<M;m++) {
        tupd[m]=-1;
    }
    ll NSP=0; //number of special edges
    ll cwt[K];
    ll itupd[K];
    vector<pii> ttf[K]; //things to fuse
    for (ll k=0;k<K;k++) {
        if (upd[k][0]==2) {
            continue;
        }
        if (tupd[upd[k][1]]==-1) {
            cwt[NSP]=edg[upd[k][1]][2];
            //cout << "cwt["<<NSP<<"]="<<cwt[NSP]<<"\n";
            tupd[upd[k][1]]=NSP;
            //cout << "tupd["<<upd[k][1]<<"]="<<NSP<<"\n";
            itupd[NSP]=upd[k][1];
            NSP++;
        }
    }
    vector<array<ll,3>> vmod;
    for (ll m=0;m<M;m++) {
        if (tupd[m]==-1) {
            vmod.push_back({edg[m][2],1,m});
        }
    }
    for (ll k=0;k<K;k++) {
        if (upd[k][0]==2) {
            ll wt = upd[k][2];
            for (ll n=0;n<NSP;n++) {
                if (cwt[n]<=wt) {
                    ll eind = itupd[n];
                    ttf[k].push_back({edg[eind][0],edg[eind][1]});
                }
            }
            vmod.push_back({wt,2,k});
        } else {
            assert(upd[k][0]==1);
            cwt[tupd[upd[k][1]]]=upd[k][2];
        }
    }
    sort(vmod.begin(),vmod.end());
    for (auto A0: vmod) {
        if (A0[1]==1) {
            ll m = A0[2];
            fz(edg[m][0],edg[m][1]);
        } else {
            rbk.clear();
            ll k = A0[2];
            for (pii p0: ttf[k]) {
                fz(p0.first,p0.second);
            }
            ll xc = upd[k][1];
            ans[k] = sz[gt(xc)].back();
            rollbk();
        }
    }
    for (ll k=0;k<K;k++) {
        if (upd[k][0]==2) {
            cout << ans[k]<<"\n";
        }
    }
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M;
    set<ll> sw0;
    for (ll m=0;m<M;m++) {
        ll u,v,d; cin >> u >> v >> d;
        u--; v--;
        sw0.insert(d);
        edg.push_back({u,v,d});
    }
    ll Q; cin >> Q;
    const ll K = 750; //change to compile time constant (256??)
    for (ll q=0;q<Q;q++) {
        ll t,x,y; cin >> t >> x >> y;
        if (t==1) {
            x--;
            upd0.push_back({t,x,y});
            sw0.insert(y);
        } else {
            x--;
            upd0.push_back({t,x,y});
            sw0.insert(y);
        }
    }
    ll NCT = sw0.size()-1;
    map<ll,ll> mw;
    for (ll x: sw0) {
        mw[x]=(NCT--);
    }
    for (ll i=0;i<M;i++) {
        edg[i][2]=mw[edg[i][2]];
        //cout << "edg: "<<edg[i][0]<<" "<<edg[i][1]<<" "<<edg[i][2]<<"\n";
    }
    for (ll q=0;q<Q;q++) {
        upd0[q][2]=mw[upd0[q][2]];
    }
    for (ll kt=0;kt<=(Q/K);kt++) {
        ll xmin = K*kt; ll xmax = min(K*(kt+1),Q);
        vector<array<ll,3>> vupd;
        for (ll x=xmin;x<xmax;x++) {
            vupd.push_back(upd0[x]);
            //cout << "UPD term: "<<upd0[x][0]<<" "<<upd0[x][1]<<" "<<upd0[x][2]<<"\n";
        }
        UPD(vupd);
        for (ll x=xmin;x<xmax;x++) {
            if (upd0[x][0]==1) {
                ll b = upd0[x][1]; ll d = upd0[x][2];
                edg[b][2]=d;
            }
        }
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27