oj.uz

Submission #100469

# Submission time Handle Problem Language Result Execution time Memory
100469 2019-03-11T13:35:44 Z square1001 Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 3000 ms 28412 KB 
#include "rainbow.h"
#include <queue>
#include <vector>
#include <cassert>
using namespace std;

const vector<int> dx = { 0, 1, 0, -1 };
const vector<int> dy = { 1, 0, -1, 0 };

bool river[55][55], vis[55][55];
void init(int R, int C, int sr, int sc, int M, char *S) {
	assert(R <= 50 && C <= 50);
	--sr, --sc;
	river[sr][sc] = true;
	for(int i = 0; i < M; ++i) {
		if(S[i] == 'N') --sr;
		if(S[i] == 'S') ++sr;
		if(S[i] == 'W') --sc;
		if(S[i] == 'E') ++sc;
		river[sr][sc] = true;
	}
}

int colour(int ar, int ac, int br, int bc) {
	--ar, --ac;
	for(int i = ar; i < br; ++i) {
		for(int j = ac; j < bc; ++j) {
			vis[i][j] = false;
		}
	}
	int ans = 0;
	for(int i = ar; i < br; ++i) {
		for(int j = ac; j < bc; ++j) {
			if(vis[i][j] || river[i][j]) continue;
			queue<pair<int, int> > que; que.push(make_pair(i, j));
			while(!que.empty()) {
				pair<int, int> u = que.front(); que.pop();
				vis[u.first][u.second] = true;
				for(int k = 0; k < 4; ++k) {
					int tx = u.first + dx[k], ty = u.second + dy[k];
					if(ar <= tx && tx < br && ac <= ty && ty < bc && !river[tx][ty] && !vis[tx][ty]) {
						que.push(make_pair(tx, ty));
					}
				}
			}
			++ans;
		}
	}
	return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Execution timed out 3086 ms 28412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Execution timed out 3086 ms 28412 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 384 KB Output is correct
2 Execution timed out 3086 ms 28412 KB Time limit exceeded
3 Halted 0 ms 0 KB -