제출 #70481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70481		funcsr	무지개나라 (APIO17_rainbow)	C++17	23 / 100	392 ms	70164 KiB

rainbow

#include "rainbow.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
struct UF {
  vector<int> U, R;
  int C;
  UF(int N) {
    rep(i, N) U.pb(i), R.pb(1);
    C = N;
  }
  int find(int x) {
    if (U[x]==x)return x;
    return U[x]=find(U[x]);
  }
  void unite(int x, int y) {
    x=find(x), y=find(y);
    if (x==y)return;
    if (R[x]<R[y])swap(x,y);
    U[y]=x;
    R[x]+=R[y];
    C--;
  }
};
int H, W;
bool bad[50][50];
int id[50][50];
vector<int> both[4], both2[4];
bool yo[4][200000];

void init(int HH, int WW, int sr, int sc, int M, char *S) {
  H = HH, W = WW;
  if (H == 2) {
    map<P, bool> bad;
    int y = sr-1, x = sc-1;
    bad[P(x, y)] = true;
    rep(i, M) {
      if (S[i] == 'N') y--;
      if (S[i] == 'S') y++;
      if (S[i] == 'W') x--;
      if (S[i] == 'E') x++;
      bad[P(x, y)] = true;
    }
    rep(S, 1<<H) {
      rep(x, W) {
        bool all = true;
        rep(y, H) if ((S>>y)&1 && !bad[P(x,y)]) all = false;
        yo[S][x] = all;
      }
      rep(x, W) if (yo[S][x]) both[S].pb(x);
      rep(x, W-1) if (yo[S][x]&&yo[S][x+1]) both2[S].pb(x);
    }
  }
  else if (W <= 50 && H <= 50) {
    int y = sr-1, x = sc-1;
    bad[x][y] = true;
    rep(i, M) {
      if (S[i] == 'N') y--;
      if (S[i] == 'S') y++;
      if (S[i] == 'W') x--;
      if (S[i] == 'E') x++;
      bad[x][y] = true;
    }
  }
  else abort();
}

int colour(int ar, int ac, int br, int bc) {
  ar--, ac--, br--, bc--;
  if (H == 2) {
    int S = 0;
    for (int y=ar; y<=br; y++) S |= 1<<y;
    int l = ac, r = bc;
    int s = index(both[S], r+1)-index(both[S], l);
    if (s==0)return 1;
    s -= index(both2[S], r)-index(both2[S], l);
    s++;
    if (yo[S][l]) s--;
    if (yo[S][r]) s--;
    return s;
  }
  else if (W <= 50 && H <= 50) {
    int V = 0;
    for (int x=ac; x<=bc; x++) {
      for (int y=ar; y<=br; y++) {
        if (!bad[x][y]) id[x][y] = V++;
        else id[x][y] = -1;
      }
    }
    UF uf(V);
    for (int x=ac; x<=bc; x++) {
      for (int y=ar; y<=br; y++) {
        if (x+1<=bc && !bad[x][y] && !bad[x+1][y]) uf.unite(id[x][y], id[x+1][y]);
        if (y+1<=br && !bad[x][y] && !bad[x][y+1]) uf.unite(id[x][y], id[x][y+1]);
      }
    }
    return uf.C;
  }
  else abort();
}

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