Submission #1263070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263070		sasde	Collapse (JOI18_collapse)	C++20	0 / 100	263 ms	18280 KiB

collapse

#include<bits/stdc++.h>
#include "collapse.h"
using namespace std;
#define sz(a) (int)a.size()
#define all(x) x.begin(),x.end()
#define ii pair<int,int>
#define se second
#define fi first
#define pb push_back
#define emb emplace_back
const int N=1e5+5,block=400;
int chiso[N];
map<ii,int>M;
bool k[N];
struct DSUrollback {
    struct State {
        int u, v, rku, rkv, timer,sz;
    };

    int n,sz;
    vector<int> par, rk;
    vector<State> history;

    DSUrollback() : n(0) {} 

    DSUrollback(int _n) : n(_n), par(_n + 5), rk(_n + 5, 0) {
        history.clear();
        sz=0;
        for (int i = 1; i <= n; ++i) par[i] = i;
    }

    void build(int _n) {
        *this = DSUrollback(_n);
    }

    int find(int u) {
        while (par[u] != u) u = par[u];
        return u;
    }

    bool join(int u, int v, int timer) {
        u = find(u);
        v = find(v);
        if (u == v) return false;
        if (rk[u] < rk[v]) std::swap(u, v);
        history.push_back({u, v, rk[u], rk[v], timer,sz});
        ++sz;
        par[v] = u;
        if (rk[u] == rk[v]) rk[u]++;

        return true;
    }

    void rollback(int timer) {
        while (!history.empty() && history.back().timer >= timer) {
            State s = history.back(); history.pop_back();
            par[s.u] = s.u;
            par[s.v] = s.v;
            rk[s.u] = s.rku;
            rk[s.v] = s.rkv;
            sz=s.sz;
        }
    }
};
vector<int>up[N],down[N],req[N],upB[N],downB[N];
bool vis[N];
vector<int> simulateCollapse(int node,vector<int>t,vector<int>x,vector<int>y,vector<int>w,vector<int>p){
    int query=sz(w),edge=sz(t);
    vector<int>ans(query);
    vector<int>vitri(query);
    iota(all(vitri),0);
    sort(all(vitri),[&](int x,int y){
        return w[x]<w[y];
    });
    // for(auto x:vitri)cout <<x<<" ";
    for(int i=0;i<edge;++i){
        if(x[i]>y[i])swap(x[i],y[i]);
        if(t[i]==0)M[{x[i],y[i]}]=i;
        else chiso[i]=M[{x[i],y[i]}];
    }
    int j=0;
    for(int _=0;_<edge;_+=block){
        int L=_,R=min(edge-1,_+block-1);
        vector<int>del,ups,downs,checku(node,0),checkd(node,0);
        while(j<query&&w[vitri[j]]<=R){
            req[p[vitri[j]]].emb(vitri[j]);
            ++j;
        }
        for(int i=L;i<=R;++i){
            if(t[i]==0){
                upB[y[i]].emb(i);
                downB[x[i]].emb(i);
                checkd[x[i]]=1;
                checku[y[i]]=1;
                // cout <<node<<" "<<x[i]<<" "<<y[i]<<'\n';
            }
            else if(chiso[i]<L)del.emb(i),vis[chiso[i]]=true;;
        }
        for(int i=0;i<node;++i){
            if(checku[i])ups.emb(i);
        }
        for(int i=node-1;i>=0;--i)
            if(checkd[i])downs.emb(i);

        DSUrollback dsu(node);
        for(int i=0;i<node;++i){
            for(int j:up[i])if(!vis[j]){
                dsu.join(x[j],y[j],-1);
            }
            for(int j:req[i]){
                for(int k=L;k<=w[j];++k){
                    if(t[k]==1)vis[chiso[k]]=true;
                }
                for(int dele:del){
                    if(dele<=w[j])continue;
                    int _dele=chiso[dele];
                    if(y[_dele]<=i){
                        dsu.join(x[_dele],y[_dele],1);
                    }
                }
                for(auto k:ups){
                    if(k>i)break;
                    for(auto l:upB[k]){
                        if(!vis[l]&&l<=w[j]){
                            // cout <<x[l]<<" "<<y[l]<<'\n';
                            dsu.join(x[l],y[l],1);
                        }
                    }
                }
                // cout <<i+1<<" "<<dsu.sz<<'\n';
                ans[j]+=i+1-dsu.sz;
                dsu.rollback(1);
                for(int k=L;k<=w[j];++k){
                    if(t[k]==1&&chiso[k]>=L)vis[chiso[k]]=false;
                }
            }
        }

        dsu.build(node);
        for(int i=node-1;i>=0;--i){
            for(int j:down[i])if(!vis[j]){
                dsu.join(x[j],y[j],-1);
            }
            for(int j:req[i]){
                for(int k=L;k<=w[j];++k){
                    if(t[k]==1)vis[chiso[k]]=true;
                }
                for(int dele:del){
                    if(dele<=w[j])continue;
                    int _dele=chiso[dele];
                    if(x[_dele]>i){
                        dsu.join(x[_dele],y[_dele],1);
                    }
                }
                for(auto k:downs){
                    if(k<=i)break;
                    for(auto l:downB[k]){
                        if(!vis[l]&&l<=w[j]){
                            // cout <<x[l]<<" "<<y[l]<<'\n';
                            dsu.join(x[l],y[l],1);
                        }
                    }
                }
                // cout <<i+1<<" "<<dsu.sz<<'\n';
                ans[j]+=node-(i+1)-dsu.sz;
                dsu.rollback(1);
                for(int k=L;k<=w[j];++k){
                    if(t[k]==1&&chiso[k]>=L)vis[chiso[k]]=false;
                }
            }
            req[i].clear();
        }
        for(int i=L;i<=R;++i){
            up[y[i]].emb(i);
            down[x[i]].emb(i);
            upB[y[i]].clear();
            downB[x[i]].clear();
        }

    }
    return ans;

}
//  main()
//  {
//    srand(time(0));
//      ios_base::sync_with_stdio(false);
//      cin.tie(NULL);
//      cout.tie(NULL);
//      #define task "xs"
//      if(fopen(task".inp","r")){
//        freopen(task".inp","r",stdin);
//        freopen(task".out","w",stdout);
//      }
//      int node;
//      vector<int>t,x,y,w,q;
//      cin >> node;
//      int a,b,c;
//      while(cin >>a >> b >> c){
//          if(!a&&!b&&!c)break;
//          t.emb(a);
//          x.emb(b);
//          y.emb(c);
// //         cout <<a<<" "<<b<<" "<<c<<'\n';
//      }
//      while(cin >> a >> b){
//          w.emb(a);
//          q.emb(b);
//      }
//      vector<int>res=simulateCollapse(node,t,x,y,w,q);
//      for(auto x:res)cout <<x<<'\n';
//  }
/*
3
0 1 2
0 1 3
0 2 3
1 2
2 3
*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35