Submission #948461

#TimeUsernameProblemLanguageResultExecution timeMemory
948461vjudge1Land of the Rainbow Gold (APIO17_rainbow)C++17
0 / 100
481 ms1048576 KiB
#include "rainbow.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define size(x) (int)x.size() template<class S, class T> bool chmin(S& a, const T& b) { return a > b ? (a = b) == b : false; } template<class S, class T> bool chmax(S& a, const T& b) { return a < b ? (a = b) == b : false; } const vector<int> dx = {0, 0, -1, 1}; const vector<int> dy = {-1, 1, 0, 0}; int n, m, x, y, k; string s; vector<vector<char>> g; vector<vector<bool>> vis; vector<int> pref[2], cmp; void init(int R, int C, int sr, int sc, int M, char* S) { n = R, m = C, x = sr - 1, y = sc - 1, k = M, s = S; g.resize(n); vis.resize(n); for (int i = 0; i < n; ++i) { g[i].assign(m, '.'); vis[i].assign(m, false); } g[x][y] = '#'; for (int i = 0; i < k; ++i) { if (s[i] == 'N') x--; else if (s[i] == 'S') x++; else if (s[i] == 'E') y++; else y--; g[x][y] = '#'; } if (n == 2) { pref[0].resize(m); pref[1].resize(m); cmp.resize(m); for (int i = 0; i < 2; ++i) { pref[i][0] = g[i][0] == '.'; for (int j = 1; j < m; ++j) { int add = 0; if (g[i][j] == '.' && g[i][j - 1] == '#') { add = 1; } pref[i][j] = pref[i][j - 1] + add; } } if (g[0][0] == '.' || g[1][0] == '.') cmp[0] = 1; else cmp[0] = 0; for (int j = 1; j < m; ++j) { int add = 1; if (g[0][j] == '.' && g[0][j - 1] == '.') add = 0; if (g[1][j] == '.' && g[1][j - 1] == '.') add = 0; cmp[j] = cmp[j - 1] + add; } } } bool check(int i, int j, int ar, int ac, int br, int bc) { return i >= ar && i <= br && j >= ac && j <= bc; } void dfs(int i, int j, int ar, int ac, int br, int bc) { vis[i][j] = true; for (int idx = 0; idx < 4; ++idx) { int I = i + dx[idx], J = j + dy[idx]; if (check(I, J, ar, ac, br, bc) && !vis[I][J] && g[I][J] != '#') { dfs(I, J, ar, ac, br, bc); } } } int colour(int ar, int ac, int br, int bc) { ar--, ac--, br--, bc--; if (n == 2) { int cnt = 0; if (ar == br) { cnt = pref[ar][bc]; if (ac) cnt -= pref[ar][ac - 1]; } else { cnt = cmp[bc]; if (ac) { cnt -= cmp[ac - 1]; int add = 0; if (g[0][ac] == '.' && g[0][ac - 1] == '.') add = 1; if (g[1][ac] == '.' && g[1][ac] - 1 == '.') add = 1; cnt += add; } } return cnt; } else { int cnt = 0; for (int i = ar; i <= br; ++i) { for (int j = ac; j <= bc; ++j) { if (!vis[i][j] && g[i][j] == '.') { cnt++; dfs(i, j, ar, ac, br, bc); } } } for (int i = ar; i <= br; ++i) { for (int j = ac; j <= bc; ++j) { vis[i][j] = false; } } return cnt; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...