제출 #972385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
972385		vjudge1	무지개나라 (APIO17_rainbow)	C++14	11 / 100	15 ms	3164 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;

const int dx[]={1, -1, 0, 0}, dy[]={0, 0, 1, -1};
bool a[100][100];
int r, c;

void init(int R, int C, int sr, int sc, int M, char *S) {
   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) {
   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: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26