제출 #1260230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260230		kamrad	무지개나라 (APIO17_rainbow)	C++20	23 / 100	3095 ms	14408 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
#define F first
#define S second
#define sz(x) x.size()

const int maxN   = 2e5 + 10;

int n, m;
int cnt[3][maxN];
bool mark[60][maxN];
bool seen[60][60];

void init(int R, int C, int sr, int sc, int M, char *T) {
	n = R;
	m = C;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			mark[i][j] = 1;

	pii cur = {sr, sc};
	mark[cur.F][cur.S] = false;
	for(int i = 0; i < M; i++) {
		char c = T[i];
		if(c == 'N') cur.F--;
		if(c == 'S') cur.F++;
		if(c == 'W') cur.S--;
		if(c == 'E') cur.S++;
		mark[cur.F][cur.S] = false;
	}
	
	for(int i = 1; i <= m; i++) {
		cnt[0][i] = cnt[0][i-1] + (mark[1][i-1] == 0 and mark[1][i] == 1);
		cnt[1][i] = cnt[1][i-1] + (mark[2][i-1] == 0 and mark[2][i] == 1);
		cnt[2][i] = cnt[2][i-1] + ((mark[1][i]|mark[2][i])&(!(mark[1][i]&mark[1][i-1]))&(!(mark[2][i]&mark[2][i-1])));
	}
}

int colour(int ar, int ac, int br, int bc) {
	if(n==2) {
		if(ar == br) {
			if(ar == 1)
				return cnt[0][bc] - cnt[0][ac-1] + (mark[1][ac]&mark[1][ac-1]);
			return cnt[1][bc] - cnt[1][ac-1] + (mark[2][ac]&mark[2][ac-1]);
		}
		return cnt[2][bc] - cnt[2][ac-1] + ((mark[1][ac]&mark[1][ac-1])|(mark[2][ac]&mark[2][ac-1]));
	}

	int ans = 0;
	vector <pii> moves = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
	for(int i = ar; i <= br; i++) {
		for(int j = ac; j <= bc; j++) {
			if(mark[i][j] and !seen[i][j]) {
				ans++;
				queue <pii> q;
				q.push({i, j});
				while(sz(q)) {
					pii u = q.front();
					q.pop();

					for(auto v : moves) {
						pii tmp = u;
						tmp.F += v.F;
						tmp.S += v.S;

						if(tmp.F >= ar and tmp.F <= br and tmp.S >= ac and tmp.S <= bc) {
							if(mark[tmp.F][tmp.S] and !seen[tmp.F][tmp.S]) {
								seen[tmp.F][tmp.S] = true;
								q.push(tmp);
							}
						}
					}
				}
			}
		}
	}
	for(int i = 0; i <= n; i++)
		for(int j = 0; j <= m; j++)
			seen[i][j] = false;
	return ans;
}

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