제출 #54850

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54850		top34051	무지개나라 (APIO17_rainbow)	C++17	0 / 100	3037 ms	53188 KiB

rainbow

//Subtask 3

#include "rainbow.h"
#include<bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 2e5 + 5;

int n,m,k;
pii a[maxn];

int cx[10] = {0,0,1,-1,-1,-1,1,1};
int cy[10] = {1,-1,0,0,-1,1,-1,1};

set<pii> ban, good;

set<pii> vis;

void dfs(int x, int y, int r1, int c1, int r2, int c2) {
//    printf("%d %d\n",x,y);
    vis.insert({x,y});
    for(int i=0;i<8;i++) {
        pii t = {x+cx[i], y+cy[i]};
        if(!(r1<=t.X && t.X<=r2 && c1<=t.Y && t.Y<=c2)) continue;
        if(vis.find(t)!=vis.end()) continue;
        int ok = 0;
        if((t.X==r1 || t.X==r2 || t.Y==c1 || t.Y == c2) && ban.find(t)==ban.end()) ok = 1;
        else if(good.find(t)!=good.end()) ok = 1;
        if(ok) dfs(t.X, t.Y, r1,c1,r2,c2);
    }
}

void init(int R, int C, int sr, int sc, int M, char *s) {
	n = R; m = C; k = M;
	a[1] = {sr, sc};
	for(int i=0;i<k;i++) {
        a[i+2] = a[i+1];
		if(s[i]=='N') a[i+2].X--;
		if(s[i]=='E') a[i+2].Y++;
		if(s[i]=='W') a[i+2].Y--;
		if(s[i]=='S') a[i+2].X++;
	}
	k++;
	for(int i=1;i<=k;i++) {
        ban.insert({a[i].X,a[i].Y});
//        printf("ban %d %d\n",a[i].X,a[i].Y);
	}

    for(int i=1;i<=k;i++) {
        for(int j=0;j<8;j++) {
            pii t = {a[i].X + cx[j], a[i].Y + cy[j]};
            if(ban.find(t)!=ban.end()) continue;
            if(good.find(t)!=good.end()) continue;
            good.insert(t);
//            printf("good %d %d\n",t.X,t.Y);
        }
    }
}

int colour(int ar, int ac, int br, int bc) {
    //isolate
    int cnt = 0;
    for(auto t : ban) {
        if(ar<=t.X && t.X<=br && ac<=t.Y && t.Y<=bc) cnt++;
    }
    if(cnt==0) return 1;
    //general
    int res = 0;
    vis.clear();
    for(auto t : good) {
        if(!(ar<=t.X && t.X<=br && ac<=t.Y && t.Y<=bc)) continue;
        if(vis.find(t)!=vis.end()) continue;
        dfs(t.X,t.Y,ar,ac,br,bc);
        res++;
    }
    return res;
}

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