Submission #900237

#TimeUsernameProblemLanguageResultExecution timeMemory
900237vjudge1Land of the Rainbow Gold (APIO17_rainbow)C++17
11 / 100
14 ms964 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; #define ii pair<int,int> const int N = 55; int grid[N][N]; int rows, cols; map<char,ii> to = {{'N', {-1, 0}}, {'S', {1, 0}}, {'W', {0, -1}}, {'E', {0, 1}}}; int arriba[N], abajo[N], ambos[N]; void init(int R, int C, int sr, int sc, int M, char *s){ rows = R; cols = C; sr--, sc--; ii pos = {sr, sc}; grid[pos.first][pos.second] = 1; for(int i=0; i<M; ++i){ char c = s[i]; pos.first += to[c].first; pos.second += to[c].second; grid[pos.first][pos.second] = 1; } // if(rows == 2){ // // subtask 2 // arriba[0] = (grid[0][0] != 1); // abajo[0] = (grid[1][0] != 1); // for(int i=1; i<cols; ++i){ // arriba[i] = (grid[0][i-1] == 1 && grid[0][i] == 0); // abajo[i] = (grid[1][i-1] == 1 && grid[1][i] == 0); // } // for(int i=1; i<cols; ++i){ // arriba[i] += arriba[i-1]; // abajo[i] += abajo[i-1]; // } // // ambos // ambos[0] = (grid[0][0] == 0 or grid[1][0] == 0); // for(int i=1; i<cols; ++i){ // if(grid[0][i-1] == 1 && grid[1][i-1] == 1){ // ambos[i] = (grid[0][i] == 0 or grid[1][i] == 0); // } // } // for(int i=1; i<cols; ++i){ // ambos[i] += ambos[i-1]; // } // } } void clear(){ for(int i=0; i<rows; ++i){ for(int j=0; j<cols; ++j){ if(grid[i][j] == 2) grid[i][j] = 0; } } } vector<ii> mov = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; void dfs(int i, int j, int ar, int ac, int br, int bc){ for(auto tmp : mov){ int ni = i + tmp.first; int nj = j + tmp.second; if(ni >= ar && ni <= br && nj >= ac && nj <= bc && grid[ni][nj] == 0){ grid[ni][nj] = 2; dfs(ni, nj, ar, ac, br, bc); } } } int colour(int ar, int ac, int br, int bc){ ar--, ac--; br--, bc--; // if(rows == 2){ // // subtask 2 // if(ar+1 == br){ // // ambos // int res = ambos[bc]; // if(ac > 0){ // res -= ambos[ac-1]; // } // return res; // } // // arriba // if(ar == 0){ // int res = arriba[bc]; // if(ac > 0){ // res -= arriba[ac-1]; // } // return res; // } // // abajo // assert(ar == 1); // int res = abajo[bc]; // if(ac > 0){ // res -= abajo[ac-1]; // } // return res; // } // subtask 1 int ans = 0; for(int i=ar; i<=br; ++i){ for(int j=ac; j<=bc; ++j){ if(grid[i][j] == 0){ ans++; grid[i][j] = 2; dfs(i, j, ar, ac, br, bc); } } } clear(); return ans; }
#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...