Submission #983458

#TimeUsernameProblemLanguageResultExecution timeMemory
983458stegatxins0Land of the Rainbow Gold (APIO17_rainbow)C++17
11 / 100
3049 ms13732 KiB
#include <bits/stdc++.h> using namespace std; #include "rainbow.h" #ifdef DEBUG #include "debug.cpp" #else #define dbg(...) #define dbgarr(...) #endif const int mxN = 1001; bool river[mxN][mxN], visited[mxN][mxN]; // {{{ HASHMAP #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; struct chash { const uint64_t C = (long long)(4e18 * acos(0)) | 71; const uint32_t RANDOM = chrono::steady_clock::now().time_since_epoch().count(); size_t operator()(uint64_t x) const { return __builtin_bswap64((x ^ RANDOM) * C); } }; // }}} int R,C; void init(int _R, int _C, int sr, int sc, int M, char *S) { R = _R, C = _C; memset(river,0,sizeof(river)); int y = sr, x = sc; gp_hash_table<char, pair<int,int>> mp; // dy, dx; // unordered_map<char,pair<int,int>> mp; mp['N'] = {-1, 0}; mp['S'] = {1, 0}; mp['W'] = {0, -1}; mp['E'] = {0, 1}; river[y][x] = 1; for(int i=0; i<M; i++){ y += mp[S[i]].first; x += mp[S[i]].second; river[y][x] = 1; dbg(y,x); } } const int dy[4] = {-1, 1, 0, 0}; const int dx[4] = {0, 0, -1, 1}; void dfs(int y, int x, int ar, int ac, int br, int bc){ visited[y][x] = 1; for(int i=0; i<4; i++){ int newy = y + dy[i]; int newx = x + dx[i]; if(newy >= ar && newx >= ac && newy <= br && newx <= bc && !river[newy][newx] && !visited[newy][newx]){ dfs(newy, newx, ar, ac, br, bc); } } } int colour(int ar, int ac, int br, int bc) { memset(visited,0,sizeof(visited)); int ans = 0; for(int y=ar; y<=br; y++){ for(int x=ac; x<=bc; x++){ if(!river[y][x] && !visited[y][x]){ dfs(y,x,ar,ac,br,bc); ans++; } } } 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...