제출 #904314

#제출 시각아이디문제언어결과실행 시간메모리
904314shezitt무지개나라 (APIO17_rainbow)C++14
23 / 100
3052 ms103956 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; #define ii pair<int,int> #define dbg(x) cerr << #x << ": " << x << endl #define raya cerr << "=================" << endl #define pb push_back const int N = 2e5+5; vector<vector<int>> grid; 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]; set<ii> nodes; set<pair<ii,ii>> edges; vector<ii> getNodes(int row, int col){ vector<ii> res; res.pb({row, col}); res.pb({row+1, col}); res.pb({row, col+1}); res.pb({row+1, col+1}); return res; } void insertNodes(int row, int col){ nodes.insert({row, col}); nodes.insert({row+1, col}); nodes.insert({row, col+1}); nodes.insert({row+1, col+1}); edges.insert({{row, col}, {row+1, col}}); edges.insert({{row, col}, {row, col+1}}); edges.insert({{row+1, col}, {row+1, col+1}}); edges.insert({{row, col+1}, {row+1, col+1}}); } set<ii> nodosSnake; void init(int R, int C, int sr, int sc, int M, char *s){ rows = R; cols = C; sr--, sc--; if(rows == 2){ grid.assign(3, vector<int>(cols+1, 0)); } else if(rows*cols <= 1e6) { grid.assign(rows+1, vector<int>(cols+1, 0)); } if(rows*cols <= 1e6){ 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] == 0); abajo[0] = (grid[1][0] == 0); 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 && grid[1][0] == 0); for(int i=1; i<cols; ++i){ if(grid[0][i-1] == 1 or grid[1][i-1] == 1){ ambos[i] = (grid[0][i] == 0 && grid[1][i] == 0); } } for(int i=1; i<cols; ++i){ ambos[i] += ambos[i-1]; } } // subtask 3 ii pos = {sr, sc}; nodosSnake.insert({sr, sc}); for(int i=0; i<M; ++i){ char c = s[i]; pos.first += to[c].first; pos.second += to[c].second; nodosSnake.insert(pos); } } 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 = arriba[bc] + abajo[bc]; int quitar = ambos[bc]; if(ac > 0){ res -= arriba[ac-1] - (grid[0][ac-1] == 0 && grid[0][ac] == 0); res -= abajo[ac-1] - (grid[1][ac-1] == 0 && grid[1][ac] == 0); quitar -= ambos[ac-1] - (grid[0][ac-1] == 0 && grid[0][ac] == 0 && grid[1][ac-1] == 0 && grid[1][ac] == 0); } res -= quitar; return res; } // arriba if(ar == 0){ int res = arriba[bc]; if(ac > 0){ res -= arriba[ac-1] - (grid[0][ac-1] == 0 && grid[0][ac] == 0); } return res; } // abajo assert(ar == 1); int res = abajo[bc]; if(ac > 0){ res -= abajo[ac-1] - (grid[1][ac-1] == 0 && grid[1][ac] == 0); } return res; } if(rows*cols <= 1e6){ // 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; } // only one query (subtask 3) int tamSnake = 0; for(auto node : nodosSnake){ if(node.first >= ar && node.first <= br && node.second >= ac && node.second <= bc){ tamSnake++; insertNodes(node.first, node.second); } } bool ok = 0; for(int col=ac; col<=bc; ++col){ vector<ii> tmp = getNodes(ar-1, col); for(auto node : tmp){ ok |= nodes.count(node); } tmp = getNodes(br+1, col); for(auto node : tmp){ ok |= nodes.count(node); } } for(int row=ar; row<=br; ++row){ vector<ii> tmp = getNodes(row, ac-1); for(auto node : tmp){ ok |= nodes.count(node); } tmp = getNodes(row, bc+1); for(auto node : tmp){ ok |= nodes.count(node); } } if(ok){ // include the border for(int col=ac; col<=bc; ++col){ insertNodes(ar-1, col); insertNodes(br+1, col); } for(int row=ar; row<=br; ++row){ insertNodes(row, ac-1); insertNodes(row, bc+1); } } int ans = 2 - (int)nodes.size() + (int)edges.size() - ok; // quitar snake size ans -= tamSnake; // quitar border size si es que fue incluido if(ok){ ans -= (br-ar+1) * 2 + (bc-ac+1) * 2; } 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...