oj.uz

Submission #540799

# Submission time Handle Problem Language Result Execution time Memory
540799 2022-03-21T18:56:28 Z LucaDantas Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 31 ms 596 KB 
#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;

constexpr int maxn = 55*55, lado = 55;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

struct DSU {
	int pai[maxn], peso[maxn];
	void init() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
	int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
	void join(int a, int b) {
		a = find(a), b = find(b);
		if(a == b) return;
		if(peso[a] < peso[b])
			swap(a, b);
		pai[b] = a;
		peso[a] += peso[b];
	}
} dsu;

bool mark[lado][lado];

void dfs(int x, int y, int here, int moves, char *S) {
	mark[x][y] = 1;
	if(here == moves) return;
	char c = S[here];
	if(c == 'N') dfs(x-1, y, here+1, moves, S);
	else if(c == 'S') dfs(x+1, y, here+1, moves, S);
	else if(c == 'W') dfs(x, y-1, here+1, moves, S);
	else if(c == 'E') dfs(x, y+1, here+1, moves, S);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
	if(max(R, C) > 50) assert(0);
	dfs(sr, sc, 0, M, S);
}

int get(int a, int b) { return a * (51) + b; }

int colour(int ar, int ac, int br, int bc) {
	dsu.init();
	for(int r = ar; r <= br; r++) {
		for(int c = ac; c <= bc; c++) {
			if(mark[r][c]) continue;
			for(int k = 0; k < 4; k++)
				if(!mark[r+dx[k]][c+dy[k]])
					dsu.join(get(r,c), get(r + dx[k], c + dy[k]));
		}
	}
	static vector<int> siuu; siuu.clear();
	for(int r = ar; r <= br; r++)
		for(int c = ac; c <= bc; c++)
			if(!mark[r][c])
				siuu.push_back(dsu.find(get(r, c)));
	sort(siuu.begin(), siuu.end());
	return unique(siuu.begin(), siuu.end()) - siuu.begin();
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 13 ms 348 KB Output is correct
3 Incorrect 31 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 468 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 596 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 13 ms 348 KB Output is correct
3 Incorrect 31 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 13 ms 348 KB Output is correct
3 Incorrect 31 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -