oj.uz

Submission #1117140

# Submission time Handle Problem Language Result Execution time Memory
1117140 2024-11-22T21:03:58 Z pedroslrey Land of the Rainbow Gold (APIO17_rainbow) C++17
0 / 100
 925 ms 1048576 KB 
#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> M;

vector<vector<int>> pref;
vector<pair<int, int>> pos;

void init(int n, int m, int sx, int sy, int sl, char *serp) {
	M.assign(n, vector<int>(m));

	--sx; --sy;
	map<char, int> sdx{{'N', -1}, {'S', 1}};
	map<char, int> sdy{{'W', -1}, {'E', 1}};
	M[sx][sy] = true;
	for (int i = 0; i < sl; ++i) {
		char c = serp[i];

		sx += sdx[c]; sy += sdy[c];
		M[sx][sy] = -1;
	}

	// int comp = 0;
	// pref.assign(n, vector<int>(m));
	// for (int i = 0; i < n; ++i)
	// 	for (int j = 0; j < m; ++j)
	// 		if (M[i][j] == 0) {
	// 			pref[i][j] = 1;
	// 			pos.emplace_back(i, j);
	// 			dfs(i, j, ++comp);
	// 		}

	// for (int i = 0; i < n; ++i)
	// 	for (int j = 0; j < m; ++j)
	// 		pref[i][j] += (i > 0 ? pref[i-1][j] : 0) 
	// 					+ (j > 0 ? pref[i][j-1] : 0) 
	// 					- (i > 0 && j > 0 ? pref[i-1][j-1] : 0);
}

// int grid_sum(int x1, int y1, int x2, int y2) {
// 	return pref[x2][y2]
// 		   - (x1 > 0 ? pref[x1 - 1][y2] : 0)
// 		   - (y1 > 0 ? pref[x2][y1 - 1] : 0) 
// 		   + (x1 > 0 && y1 > 0 ? pref[x1 - 1][y1 - 1] : 0);
// }

int colour(int x1, int y1, int x2, int y2) {
	--x1; --y1; --x2; --y2;	

	function<void (int, int, int)> dfs = [&](int x, int y, int c) {
		M[x][y] = c;

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

		for (int k = 0; k < 4; ++k) {
			int nx = x + dx[k], ny = y + dy[k];

			if (nx < x1 || nx > x2 || ny < y1 || ny > y2) continue;
			if (M[nx][ny] == c || M[nx][ny] == -1) continue;

			dfs(nx, ny, c);
		}
	};

	static int cnt = 0;
	++cnt;

	int ans = 0;
	for (int i = x1; i <= x2; ++i)
		for (int j = y1; j <= y2; ++j)
			if (M[i][j] != -1 && M[i][j] != cnt) {
				++ans;
				dfs(i, j, cnt);
			}

	return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

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

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -