oj.uz

Submission #433480

# Submission time Handle Problem Language Result Execution time Memory
433480 2021-06-19T21:14:46 Z rqi Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 31 ms 836 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define ins insert
#define pb push_back

void ckmin(int& a, int b){
	a = min(a, b);
}

void ckmax(int& a, int b){
	a = max(a, b);
}

vector<char> dchar = vector<char>{'S', 'E', 'N', 'W'};
vi dx = vi{1, 0, -1, 0};
vi dy = vi{0, 1, 0, -1};

bool filled[55][55];

struct DSU{
	vi e;
	void init(int N){
		e = vi(N, -1);
	}

	int get(int a){
		if(e[a] < 0) return a;
		e[a] = get(e[a]);
		return e[a];
	}

	bool unite(int a, int b){
		a = get(a);
		b = get(b);
		if(a == b) return 0;
		if(-e[a] < -e[b]) swap(a, b);
		e[a]+=e[b];
		e[b] = a;
		return 1;
	}
};
void init(int R, int C, int sr, int sc, int M, char *S) {
	for(int i = 0; i <= M; i++){
		filled[sr][sc] = 1;
		if(i < M){
			for(int d = 0; d < 4; d++){
				if(S[i] == dchar[d]){
					sr+=dx[d];
					sc+=dy[d];
					break;
				}
			}
		}
	}
}

int colour(int ar, int ac, int br, int bc) {
	DSU dsu;
	dsu.init(55*55);
	for(int i = ar; i <= br; i++){
		for(int j = ac; j <= bc; j++){
			if(!filled[i][j]){
				for(int d = 0; d < 4; d++){
					int new_r = i+dx[d];
					int new_c = j+dy[d];
					if(ar <= new_r && new_r <= br && ac <= new_c && new_c <= bc && !filled[new_r][new_c]){
						dsu.unite(55*i+j, 55*new_r+new_c);
					}
				}
			}
		}
	}

	int ans = 0;
	for(int i = ar; i <= br; i++){
		for(int j = ac; j <= bc; j++){
			if(!filled[i][j]){
				if(dsu.get(55*i+j) == 55*i+j){
					ans++;
				}
			}
		}
	}
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 204 KB Output is correct
2 Correct 11 ms 204 KB Output is correct
3 Correct 31 ms 308 KB Output is correct
4 Correct 31 ms 340 KB Output is correct
5 Correct 10 ms 344 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 280 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 25 ms 452 KB Output is correct
12 Correct 20 ms 344 KB Output is correct
13 Correct 12 ms 332 KB Output is correct
14 Correct 5 ms 332 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct

Subtask #2
0 / 12.0

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

Subtask #3
0 / 24.0

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

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 204 KB Output is correct
2 Correct 11 ms 204 KB Output is correct
3 Correct 31 ms 308 KB Output is correct
4 Correct 31 ms 340 KB Output is correct
5 Correct 10 ms 344 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 280 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 25 ms 452 KB Output is correct
12 Correct 20 ms 344 KB Output is correct
13 Correct 12 ms 332 KB Output is correct
14 Correct 5 ms 332 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Runtime error 2 ms 836 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 204 KB Output is correct
2 Correct 11 ms 204 KB Output is correct
3 Correct 31 ms 308 KB Output is correct
4 Correct 31 ms 340 KB Output is correct
5 Correct 10 ms 344 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 280 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 25 ms 452 KB Output is correct
12 Correct 20 ms 344 KB Output is correct
13 Correct 12 ms 332 KB Output is correct
14 Correct 5 ms 332 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Runtime error 2 ms 836 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -