Submission #1256126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256126		minhpk	Collapse (JOI18_collapse)	C++20	0 / 100	63 ms	98236 KiB

collapse

#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
int a,b,c;

struct dsu{
      int par[1000005];
      int sz[1000005];
      int cnt;
      vector <pair<int,int>> st;
      void init(){
          cnt=0;
          for (int i=1;i<=a;i++){
               par[i]=i;
               sz[i]=1;
          }
      }
      int find(int u){
          if (par[u]==u){
              return u;
          }
          return find(par[u]);
      }
      void join(int x,int y){
           x=find(x);
           y=find(y);
           if (x==y){
              st.push_back({-1,-1});
           }
           if (sz[x]<sz[y]){
               swap(x,y);
           }
           st.push_back({x,y});
           par[y]=x;
           sz[x]+=sz[y];
           cnt++;
      }

      void rollback(){
          auto [x,y] =st.back();
          st.pop_back();
          if (x==-1){
              return;
          }
          cnt--;
          par[y]=y;
          sz[x]-=sz[y];
      }
};
dsu d;
int block=320;
vector <int> q[1000005];
set<pair<int,int>> s;
vector <pair<int,int>> v[1000005];
vector<int> pos[1000005];
vector <int> z[1000005];

vector<int> simulateCollapse(int N,vector<int> T,vector<int> X,vector<int> Y,vector<int> W,vector<int> P){
       a=N;
       b=T.size();
       c=W.size();
       vector <int> res(c,0);
       for (int i=0;i<c;i++){
            q[W[i]].push_back(i);
       }
       for (int t=0;t<b;t+=block){
            set<pair<int,int>> s1;
            for (int i=t;i<min(t+block,b);i++){
                 int x=X[i];
                 int y=Y[i];
                 if (x>y){
                     swap(x,y);
                 }
                 if (s.find({x,y})!=s.end()){
                     s.erase({x,y});
                     s1.insert({x,y});
                 }
            }
            for (int i=t;i<min(t+block,b);i++){
                 int x=X[i];
                 int y=Y[i];
                 if (x>y){
                     swap(x,y);
                 }
                 if (T[i]){
                     s1.erase({x,y});
                 }else{
                     s1.insert({x,y});
                 }
                 for (auto p:s1){
                      v[i].push_back(p);
                 }
                 for (auto p:q[i]){
                      pos[P[p]].push_back(p);
                 }
            }

            d.init();
            for (int i=0;i<=a;i++){
                 z[i].clear();
            }
            for (auto p:s){
                 z[p.second].push_back(p.first);
            }
            for (int i=0;i<a;i++){
                 for (auto p:z[i]){
                     d.join(p,i);
                 }
                 for (auto p:pos[i]){
                      for (auto j:v[W[p]]){
                           if (j.second<=P[p]){
                               d.join(j.first,j.second);
                           }
                      }
                      res[p]+=d.cnt;
                      for (auto j:v[W[p]]){
                           if (j.second<=P[p]){
                               d.rollback();
                           }
                      }
                 }
            }


            d.init();
            for (int i=0;i<=a;i++){
                 z[i].clear();
            }
            for (auto p:s){
                 z[p.first].push_back(p.second);
            }
            for (int i=a-1;i>=0;i--){
                 for (auto p:pos[i]){
                      for (auto j:v[W[p]]){
                           if (j.second<=P[p]){
                               d.join(j.first,j.second);
                           }
                      }
                      res[p]+=d.cnt;
                      for (auto j:v[W[p]]){
                           if (j.second<=P[p]){
                               d.rollback();
                           }
                      }
                 }
                 for (auto p:z[i]){
                     d.join(p,i);
                 }
            }

            for (auto p:s1){
                 s.insert(p);
            }
       }
      for (int i=0;i<c;i++){
           res[i]=a-res[i];
      }
      return res;
}

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