제출 #1254669

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254669		minhpk	Collapse (JOI18_collapse)	C++20	0 / 100	71 ms	121784 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
int a,b,c;
vector<int> t;
vector<int> z;
vector<int> z1;
vector<int> w;
vector<int> w1;
vector <int> res;
map<pair<int,int>,int> m;
struct edge{
      int x,y,l,r;
};
vector <edge> vec;
vector <pair<int,int>> pos[1000005];
bool cmp(pair<int,int> a,pair<int,int> b){
     return max(a.first,a.second)<max(b.first,b.second);
}
bool cmp1(pair<int,int> a,pair<int,int> b){
     return min(a.first,a.second)>min(b.first,b.second);
}
struct ST{
      int f[4000005]={0};
      int lazy[4000005]={0};

      void build(int id,int l,int r){
           lazy[id]=0;
           if (l==r){
              f[id]=0;
              return;
           }
           int mid=(l+r)/2;
           build(id*2,l,mid);
           build(id*2+1,mid+1,r);
           f[id]=f[id*2]+f[id*2+1];
      }

      void push(int id){
          if (lazy[id]!=0){
              lazy[id*2]+=lazy[id];
              lazy[id*2+1]+=lazy[id];

              f[id*2]+=lazy[id];
              f[id*2+1]+=lazy[id];

              lazy[id]=0;
          }
      }
      void update(int id,int l,int r,int x,int y,int val){
           if (x>r || y<l){
               return;
           }
           if (l>=x && y>=r){
               f[id]+=val;
               lazy[id]+=val;
               return;
           }
           int mid=(l+r)/2;
           push(id);
           update(id*2,l,mid,x,y,val);
           update(id*2+1,mid+1,r,x,y,val);
           f[id]=f[id*2]+f[id*2+1];
      }
      int get(int id,int l,int r,int pos){
          if (l==r){
             return f[id];
          }
          int mid=(l+r)/2;
          push(id);
          if (pos<=mid){
              return get(id*2,l,mid,pos);
          }else{
              return get(id*2+1,mid+1,r,pos);
          }
      }
};
ST f1;


vector<pair<int,int>> f[4000005];

void update(int id,int l,int r,int x,int y,pair<int,int> val){
     if (x>r || y<l){
         return;
     }
     if (l>=x && y>=r){
         f[id].push_back(val);
         return;
     }
     int mid=(l+r)/2;
     update(id*2,l,mid,x,y,val);
     update(id*2+1,mid+1,r,x,y,val);
}


int par[1000005];
int sz[1000005];
stack<pair<pair<int,int>,int>> st;
int find(int u){
    if (par[u]==u){
        return u;
    }
    return find(par[u]);
}
bool join(int x,int y,int id){
    x=find(x);
    y=find(y);
    if (x==y){
        return false;
    }
    if (sz[x]<sz[y]){
        swap(x,y);
    }
    st.push({{x,sz[x]},id});
    st.push({{y,sz[y]},id});
    par[y]=x;
    sz[x]+=sz[y];
    return true;
}

void rollback(int id,int type){
    while (st.size() && st.top().second==id){
           int x=st.top().first.first;
           int p=st.top().first.second;
           sz[x]=p;
           par[x]=x;
           st.pop();

           int y=st.top().first.first;
           p=st.top().first.second;
           sz[y]=p;
           par[y]=y;
           st.pop();

         if (type==1){
             int pre=max(x,y);
             f1.update(1,0,a,pre,a,1);
         }else{
             int pre=min(x,y);
             f1.update(1,0,a,0,pre,1);
         }
    }
}

void dfs(int id,int l,int r){
     sort(f[id].begin(),f[id].end(),cmp);
     for (auto p:f[id]){
          int x=min(p.first,p.second);
          if (join(p.first,p.second,id)){
              f1.update(1,0,a,0,x,-1);
          }
          rollback(id,1);
     }
     if (l==r){
         for (auto p:pos[l]){
              int pre=p.second;
              int x=p.first;
              res[pre]+=f1.get(1,0,a,x);
         }
         return;
     }
     int mid=(l+r)/2;
     dfs(id*2,l,mid);
     dfs(id*2+1,mid+1,r);
     rollback(id,1);
}



void dfs1(int id,int l,int r){
     sort(f[id].begin(),f[id].end(),cmp1);
     for (auto p:f[id]){
          int x=max(p.first,p.second);
          if (join(p.first,p.second,id)){
              f1.update(1,0,a,x,a,-1);
          }
     }
     if (l==r){
         for (auto p:pos[l]){
              int pre=p.second;
              int x=p.first;
              res[pre]+=f1.get(1,0,a,x);
         }
         rollback(id,2);
         return;
     }
     int mid=(l+r)/2;
     dfs1(id*2,l,mid);
     dfs1(id*2+1,mid+1,r);
     rollback(id,2);
}


vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
      a=N;
      t=T;
      z=X;
      z1=Y;
      w=W;
      w1=P;
      b=t.size();
      c=w.size();
      res.resize(c,0);
      for (int i=1;i<=b;i++){
           int x=z[i-1];
           int y=z1[i-1];
           int type=t[i-1];
           if (type==0){
               m[{x,y}]=i;
               m[{y,x}]=i;
           }else{
               vec.push_back({x,y,m[{x,y}],i-1});
               m[{x,y}]=0;
               m[{y,x}]=0;
           }
      }

      for (auto p:m){
          if (p.second!=0){
              vec.push_back({p.first.first,p.first.second,p.second,b});
          }
      }

      for (auto p:vec){
           auto [x,y,l,r]=p;
           pair<int,int> pre={x,y};
           update(1,1,b,l,r,pre);
      }
      for (int i=0;i<c;i++){
           int w2=w[i];
           int p=w1[i];
           pos[w2+1].push_back({p,i});
      }
      f1.build(1,0,a);

      for (int i=0;i<a;i++){
           f1.update(1,0,a,i,a,1);
      }
      for (int i=0;i<=a;i++){
           par[i]=i;
           sz[i]=1;
      }
      dfs(1,1,b);
      f1.build(1,0,a);
      for (int i=0;i<=a;i++){
           par[i]=i;
           sz[i]=1;
      }
      while (st.size()){
          st.pop();
      }
      for (int i=a-1;i>=0;i--){
           f1.update(1,0,a,0,i,1);
      }
      dfs1(1,1,b);
      return res;
}

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