oj.uz

Submission #409177

# Submission time Handle Problem Language Result Execution time Memory
409177 2021-05-20T09:59:53 Z cheissmart Land of the Rainbow Gold (APIO17_rainbow) C++14
11 / 100
 3000 ms 1048580 KB 
#ifndef CHEISSMART
#include "rainbow.h"
#endif
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7;

int di[] = {1, -1, 0, 0}, dj[] = {0, 0, 1, -1};

V<pi> bad;
int R, C;

void init(int R, int C, int sr, int sc, int M, char *S) {
	::R = R, ::C = C;
	bad.EB(sr - 1, sc - 1);
	for(int i = 0; i < M; i++) {
		if(S[i] == 'N') sr--;
		else if(S[i] == 'S') sr++;
		else if(S[i] == 'W') sc--;
		else sc++;
		bad.EB(sr - 1, sc - 1);
	}
	sort(ALL(bad));
	bad.resize(unique(ALL(bad)) - bad.begin());
}

int colour(int ar, int ac, int br, int bc) {
	ar--, ac--, br--, bc--;
	V<vi> vis(R, vi(C));
	for(pi p:bad)
		vis[p.F][p.S] = 1;
 	auto ok = [&] (int i, int j) {
		return ar <= i && i <= br && ac <= j && j <= bc && vis[i][j] == 0;
	};
	function<void(int, int)> dfs = [&] (int i, int j) {
		vis[i][j] = 1;
		for(int k = 0; k < 4; k++) {
			int ii = i + di[k], jj = j + dj[k];
			if(ok(ii, jj))
				dfs(ii, jj);
		}
	};

	int cnt = 0;
	for(int i = ar; i <= br; i++) {
		for(int j = ac; j <= bc; j++) {
			if(vis[i][j] == 0) {
				cnt++;
				dfs(i, j);
			}
		}
	}
	debug(cnt);
	return cnt;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 17 ms 376 KB Output is correct
3 Correct 30 ms 572 KB Output is correct
4 Correct 31 ms 516 KB Output is correct
5 Correct 18 ms 440 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 204 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 25 ms 460 KB Output is correct
12 Correct 23 ms 332 KB Output is correct
13 Correct 23 ms 432 KB Output is correct
14 Correct 25 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Execution timed out 3089 ms 29500 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

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

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 17 ms 376 KB Output is correct
3 Correct 30 ms 572 KB Output is correct
4 Correct 31 ms 516 KB Output is correct
5 Correct 18 ms 440 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 204 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 25 ms 460 KB Output is correct
12 Correct 23 ms 332 KB Output is correct
13 Correct 23 ms 432 KB Output is correct
14 Correct 25 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Execution timed out 3066 ms 15684 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 17 ms 376 KB Output is correct
3 Correct 30 ms 572 KB Output is correct
4 Correct 31 ms 516 KB Output is correct
5 Correct 18 ms 440 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 204 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 25 ms 460 KB Output is correct
12 Correct 23 ms 332 KB Output is correct
13 Correct 23 ms 432 KB Output is correct
14 Correct 25 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Execution timed out 3066 ms 15684 KB Time limit exceeded
19 Halted 0 ms 0 KB -