답안 #70504 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70504	2018-08-23T04:53:57 Z	funcsr	무지개나라 (APIO17_rainbow)	C++17	12 / 100	445 ms	35520 KB

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
const int DX[4] = {-1,0,1,0}, DY[4]={0,-1,0,1};

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];
int SX, SY;
string T;

void init(int HH, int WW, int sr, int sc, int M, char *S) {
  SX=sc-1,SY=sr-1;T=string(S, S+M);
  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;
    }
  }
}

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 (false) {
  //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 {
    br++,bc++;
    //cout<<"Q=1\n";
    // Q=1
    map<P, bool> blocks;
    int x = SX, y = SY;
    blocks[P(x,y)] = true;
    vector<P> inner;
    vector<P> possible_tate, possible_yoko;
    if (ac<=x&&x<=bc&&ar<=y&&y<=br-1) possible_tate.pb(P(x, y));
    if (ac<=x+1&&x+1<=bc&&ar<=y&&y<=br-1) possible_tate.pb(P(x+1, y));
    if (ac<=x&&x<=bc-1&&ar<=y&&y<=br) possible_yoko.pb(P(x, y));
    if (ac<=x&&x<=bc-1&&ar<=y+1&&y+1<=br) possible_yoko.pb(P(x, y+1));
    if (ac<=x&&x<=bc&&ar<=y&&y<=br) inner.pb(P(x, y));
    for (char c:T) {
      if (c == 'N') y--;
      if (c == 'S') y++;
      if (c == 'W') x--;
      if (c == 'E') x++;
      if (ac<=x&&x<=bc&&ar<=y&&y<=br-1) possible_tate.pb(P(x, y));
      if (ac<=x+1&&x+1<=bc&&ar<=y&&y<=br-1) possible_tate.pb(P(x+1, y));
      if (ac<=x&&x<=bc-1&&ar<=y&&y<=br) possible_yoko.pb(P(x, y));
      if (ac<=x&&x<=bc-1&&ar<=y+1&&y+1<=br) possible_yoko.pb(P(x, y+1));
      if (ac<=x&&x<=bc&&ar<=y&&y<=br) inner.pb(P(x, y));
      blocks[P(x,y)] = true;
    }
    vector<P> tate, yoko;
    for (P p : possible_tate) if (!blocks[P(p._1-1,p._2)]||!blocks[P(p._1,p._2)]) tate.pb(p);
    for (P p : possible_yoko) if (!blocks[P(p._1,p._2-1)]||!blocks[P(p._1,p._2)]) yoko.pb(p);
    for (int y=ar; y<=br-1; y++) tate.pb(P(ac, y)), tate.pb(P(bc, y));
    for (int x=ac; x<=bc-1; x++) yoko.pb(P(x, ar)), yoko.pb(P(x, br));
    sort(all(tate)); uniq(tate);
    sort(all(yoko)); uniq(yoko);
    vector<P> pts;
    for (P p : tate) pts.pb(p), pts.pb(P(p._1, p._2+1));
    for (P p : yoko) pts.pb(p), pts.pb(P(p._1+1, p._2));
    sort(all(pts)); uniq(pts);
    UF uf(pts.size());
    for (P p : tate) {
      int u = index(pts, p), v = index(pts, P(p._1, p._2+1));
      uf.unite(u, v);
    }
    for (P p : yoko) {
      int u = index(pts, p), v = index(pts, P(p._1+1, p._2));
      uf.unite(u, v);
    }
    sort(all(inner)); uniq(inner);
    UF uf2(inner.size());
    rep(i, inner.size()) {
      P p = inner[i];
      rep(k, 4) {
        int x = p._1+DX[k], y=p._2+DY[k];
        if (!binary_search(all(inner), P(x,y))) continue;
        int t = index(inner, P(x,y));
        uf2.unite(i,t);
      }
    }
    int e = tate.size()+yoko.size();
    int v = pts.size();
    int c = uf.C;
    //cout<<"e="<<e<<", v="<<v<<", c="<<c<<"\n";
    return e-v+c-uf2.C;
  }
}

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
rainbow.cpp:174:5: note: in expansion of macro 'rep'
     rep(i, inner.size()) {
     ^~~

Subtask #1
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	117 ms	504 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	2 ms	504 KB	Output is correct
3	Correct	352 ms	29484 KB	Output is correct
4	Correct	424 ms	29948 KB	Output is correct
5	Correct	445 ms	29948 KB	Output is correct
6	Correct	379 ms	29948 KB	Output is correct
7	Correct	436 ms	29948 KB	Output is correct
8	Correct	339 ms	29948 KB	Output is correct
9	Correct	388 ms	29948 KB	Output is correct
10	Correct	383 ms	30012 KB	Output is correct
11	Correct	404 ms	30032 KB	Output is correct
12	Correct	360 ms	30032 KB	Output is correct
13	Correct	398 ms	30032 KB	Output is correct
14	Correct	379 ms	30180 KB	Output is correct
15	Correct	320 ms	30180 KB	Output is correct
16	Correct	328 ms	30180 KB	Output is correct

Subtask #3
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	30180 KB	Output is correct
2	Correct	322 ms	30180 KB	Output is correct
3	Correct	302 ms	30180 KB	Output is correct
4	Correct	432 ms	33748 KB	Output is correct
5	Correct	199 ms	33748 KB	Output is correct
6	Correct	215 ms	33748 KB	Output is correct
7	Correct	421 ms	35520 KB	Output is correct
8	Correct	73 ms	35520 KB	Output is correct
9	Correct	47 ms	35520 KB	Output is correct
10	Incorrect	34 ms	35520 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	117 ms	504 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	117 ms	504 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

답안 #70504

Compilation message

Subtask #1 0 / 11.0

Subtask #2 12.0 / 12.0

Subtask #3 0 / 24.0

Subtask #4 0 / 27.0

Subtask #5 0 / 26.0

Subtask #1
0 / 11.0

Subtask #2
12.0 / 12.0

Subtask #3
0 / 24.0

Subtask #4
0 / 27.0

Subtask #5
0 / 26.0