Submission #756661

#	Time	Username	Problem	Language	Result	Execution time	Memory
756661		khoquennguoiminhthuong	Bridges (APIO19_bridges)	C++17	100 / 100	2700 ms	5560 KiB

bridges

#include <bits/stdc++.h>
 
using namespace std;
int n,m,q;
struct canh {
    int u,v,w;
} e[500005];
int dd[200005],ans[200005];
struct disjoint_set_union_rollback {
    vector <int> lab, sz;
    stack <int> save;
    int n;
    disjoint_set_union_rollback(int _n = 0) : n(_n) {
        lab.resize(n + 1, 0);
        sz.resize(n + 1, 1);
        iota(lab.begin(),lab.end(), 0);
    }
 
    void clear() {
        while((int) save.size()) save.pop();
        fill(sz.begin(),sz.end(), 1);
        iota(lab.begin(),lab.end(), 0);
    }
 
    int find(int u) {
        assert(u <= n);
        // cout << u << '\n';
        return lab[u] == u ? u : find(lab[u]);
    }
 
    bool merge(int u, int v) {
        u = find(u), v = find(v);
        if(u == v) return false;
        if(sz[u] < sz[v]) swap(u, v);
        sz[u] += sz[v];
        lab[v] = u;
        save.push(v);
        return true;
    }
    void rollback(int ptr) {
        while((int) save.size() > ptr) {
            int v = save.top(); save.pop();
            sz[lab[v]] -= sz[v];
            lab[v] = v;
        }
    }
};
 
bool cmp(int a,int b) {
    if(e[a].w!=e[b].w)return e[a].w>e[b].w;
    return a<b;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    cin>>q;
    for(int i=1; i<=q; i++)
        cin>>e[i+m].u>>e[i+m].v>>e[i+m].w;
    const int blsize=1000;
    disjoint_set_union_rollback dsu(n+5);
    for(int l=m+1; l<=q+m; l+=blsize) {
        int r=min(l+blsize-1,m+q);
        dsu.clear();
        vector<int>change;
        vector<int>unchange;
        for(int i=l; i<=r; i++) {
            if(e[i].u==1) {
                change.push_back(i);
                dd[e[i].v]=1;
            } else unchange.push_back(i);
        }
        for(int i=1; i<=m; i++)if(dd[i]==0)unchange.push_back(i);
            else dd[i]=0;
        sort(unchange.begin(),unchange.end(),cmp);
        reverse(change.begin(),change.end());
        for(auto v:unchange) {
            if(v<=m) {
                dsu.merge(e[v].u,e[v].v);
            } else {
                int now=(int)dsu.save.size();
                for(auto vv:change) {
                    if(vv<=v&&dd[e[vv].v]==0) {
                        dd[e[vv].v]=1;
                        int id=e[vv].v;
                        if(e[vv].w>=e[v].w)dsu.merge(e[id].u,e[id].v);
                    }
                }
                for(auto vv:change) {
                    if(vv>v&&dd[e[vv].v]==0) {
                        int id=e[vv].v;
                        if(e[id].w>=e[v].w)dsu.merge(e[id].u,e[id].v);
                    }
                }
                ans[v]=dsu.sz[dsu.find(e[v].v)];
                dsu.rollback(now);
                for(auto vv:change)dd[e[vv].v]=0;
            }
        }
     for(int i=l;i<=r;i++)if(e[i].u==1){int id=e[i].v;e[id].w=e[i].w;}
    }
    for(int i=m+1; i<=m+q; i++)if(ans[i])cout<<ans[i]<<'\n';
    return 0;
}

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