제출 #972506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972506		vjudge1	무지개나라 (APIO17_rainbow)	C++14	23 / 100	74 ms	11124 KiB

rainbow

#include "rainbow.h"

#include <bits/stdc++.h>

using namespace std;

struct DSU{
   int n;
   vector<int> lab;
   int cc;
   void init(int _n){
      n=_n;
      cc=n;
      lab.assign(n+1, -1);
   }
   int find_set(int u){
      return lab[u]<0?u:lab[u]=find_set(lab[u]);
   }
   void union_sets(int u, int v){
      u=find_set(u), v=find_set(v);
      if (u!=v){
         if (lab[u]>lab[v]) swap(u, v);
         lab[u]+=lab[v];
         lab[v]=u;
         --cc;
      }
   }
} dsu, dsu1, dsu2;

const int N=2e5+10;
const int dx[]={1, -1, 0, 0}, dy[]={0, 0, 1, -1};
bool a[100][100], a2[3][N];
int pf[3][N], pf1[N], pf2[N];
int r, c;

void init(int R, int C, int sr, int sc, int M, char *S) {
   if (R==2){
      r=R, c=C;
      a2[sr][sc]=1;
      for (int i=0; i<M; ++i){
         if (S[i]=='N') --sr;
         if (S[i]=='S') ++sr;
         if (S[i]=='E') ++sc;
         if (S[i]=='W') --sc;
         a2[sr][sc]=1;
      }
      dsu.init(r*c);
      for (int i=1; i<=r; ++i) for (int j=1; j<=c; ++j){
         if (!a2[i][j]){
            for (int k=0; k<4; ++k){
               int x=i+dx[k], y=j+dy[k];
               if (x<1 || y<1 || x>r || y>c || a2[x][y]) continue;
               dsu.union_sets((i-1)*c+(j-1), (x-1)*c+(y-1));
            }
         }
      }
      dsu1.init(c), dsu2.init(c);
      for (int j=1; j<=c; ++j){
         if (!a2[1][j]){
            for (int k=2; k<4; ++k){
               int x=1, y=j+dy[k];
               if (y<1 || y>c || a2[x][y]) continue;
               dsu1.union_sets(j-1, y-1);
            }
         }
      }
      for (int j=1; j<=c; ++j){
         if (!a2[2][j]){
            for (int k=2; k<4; ++k){
               int x=2+dx[k], y=j+dy[k];
               if (y<1 || y>c || a2[x][y]) continue;
               dsu2.union_sets(j-1, y-1);
            }
         }
      }
      for (int i=1; i<=r; ++i) for (int j=1; j<=c; ++j){
         pf[i][j]=pf[i][j-1];
         if (!a2[i][j] && dsu.lab[(i-1)*c+j-1]<0) ++pf[i][j];
      }
      for (int i=1; i<=c; ++i){
         pf1[i]=pf1[i-1];
         if (!a2[1][i] && dsu1.lab[i-1]<0) ++pf1[i];
      }
      for (int i=1; i<=c; ++i){
         pf2[i]=pf2[i-1];
         if (!a2[2][i] && dsu2.lab[i-1]<0) ++pf2[i];
      }
   }else{
      r=R, c=C;
      a[sr][sc]=1;
      for (int i=0; i<M; ++i){
         if (S[i]=='N') --sr;
         if (S[i]=='S') ++sr;
         if (S[i]=='E') ++sc;
         if (S[i]=='W') --sc;
         a[sr][sc]=1;
      }
   }
}

int colour(int ar, int ac, int br, int bc) {
   if (r==2){
      set<int> st;
      int ans=0;
      if (ar==br && ar==1){
         ans=pf1[bc]-pf1[ac-1];
         if (!a2[ar][ac] && dsu1.find_set(ac-1)>=0) st.insert(dsu1.find_set(ac-1));
         if (!a2[ar][bc] && dsu1.find_set(bc-1)>=0) st.insert(dsu1.find_set(bc-1));
         for (int i:st) if (i<ac-1 || i>bc-1) ++ans;
      }else if (ar==br){
         ans=pf2[bc]-pf2[ac-1];
         if (!a2[ar][ac] && dsu2.find_set(ac-1)>=0) st.insert(dsu2.find_set(ac-1));
         if (!a2[ar][bc] && dsu2.find_set(bc-1)>=0) st.insert(dsu2.find_set(bc-1));
         for (int i:st) if (i<ac-1 || i>bc-1) ++ans;
      }else{
         ans=pf[1][bc]-pf[1][ac-1]+pf[2][bc]-pf[2][ac-1];
         if (!a2[ar][ac] && dsu.find_set(ac-1)>=0) st.insert(dsu.find_set(ac-1));
         if (!a2[ar][bc] && dsu.find_set(bc-1)>=0) st.insert(dsu.find_set(bc-1));
         if (!a2[br][ac] && dsu.find_set(c+ac-1)>=0) st.insert(dsu.find_set(c+ac-1));
         if (!a2[br][bc] && dsu.find_set(c+bc-1)>=0) st.insert(dsu.find_set(c+bc-1));
         for (int i:st) if ((i%c<ac-1 || i%c>bc-1)) ++ans;
      }
      return ans;
   }
   dsu.init((br-ar+1)*(bc-ac+1));
   for (int i=ar; i<=br; ++i) for (int j=ac; j<=bc; ++j){
      if (a[i][j]) --dsu.cc;
      else{
         for (int k=0; k<4; ++k){
            int x=i+dx[k], y=j+dy[k];
            if (x<ar || y<ac || x>br || y>bc || a[x][y]) continue;
            dsu.union_sets((i-ar)*(bc-ac+1)+(j-ac), (x-ar)*(bc-ac+1)+(y-ac));
         }
      }
   }
   return dsu.cc;
}

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26