| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 887747 | 2023-12-15T07:18:09 Z | vjudge1 | Land of the Rainbow Gold (APIO17_rainbow) | C++17 | 0 ms | 0 KB |
/****************************D A N E T****************************
*** ██████╗ █████╗ ███╗ ██╗ ███████╗ ████████╗ ***
*** ██╔══██╗ ██╔══██╗ ████╗ ██║ ██╔════╝ ╚══██╔══╝ ***
*** ██║ ██║ ███████║ ██╔██╗ ██║ █████╗ ██║ ***
*** ██║ ██║ ██╔══██║ ██║╚██╗██║ ██╔══╝ ██║ ***
*** ██████╔╝ ██║ ██║ ██║ ╚████║ ███████╗ ██║ ***
*** ╚═════╝ ╚═╝ ╚═╝ ╚═╝ ╚═══╝ ╚══════╝ ***
****************************D A N E T****************************/
#include <bits/stdc++.h>
using namespace std;
/**************************P R A G M As**************************/
#pragma GCC optimize("O3")
/**************************D E F I N Es**************************/
#define Tof_Io ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define int long long int
#define double long double
#define pb push_back
#define endl '\n'
/*****************D E F I N Es-F U N C T I O Nes*****************/
#define debug(x) cerr << #x << ": " << x << endl
#define kill(x) cout << x << endl, exit(0)
#define all(x) x.begin(),x.end()
#define yes cout << "Yes"
#define no cout <<"No"
/***************************C O N S Ty***************************/
const double PI = 3.141592653589793;
const int mod = 998244353;//1e9+7 998244353
const int inf = 1e9+9;
const int logt = 18;
const int N = 500 + 23;
/***************************B U I L Dy***************************/
int fac[N];
int inv[N];
vector<int> adj[N];
bool seen[N][N];
string str;
vector<pair<int, int> > dx = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
/****************************N O T Ey****************************/
/*
*/
/***********************F U N C T I O N es***********************/
int dnt_pow (int a, int b, int md = mod){int ans = 1; while(b){if(b&1){ans = (a*ans)%md;}a = (a*a)%md;b >>= 1;}return ans ;}
void dnt_bld (){fac[0] = 1; inv[0] = dnt_pow(fac[0],mod-2) ;for(int i = 1 ; i < N ; i++) {fac[i] = (fac[i-1] * i) % mod;inv[i] = dnt_pow( fac[i] , mod-2);}}
int dnt_lis (vector<int> v){if (v.size() == 0) {return 0;} vector<int> vc(v.size(), 0); int len = 1; vc[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = vc.begin(), e = vc.begin() + len; auto it = lower_bound(b, e, v[i]); if (it == vc.begin() + len){vc[len++] = v[i];}else{*it = v[i];}} return len;}
int dnt_ncr (int n,int r){return fac[n] * inv[r] % mod * inv[n-r] % mod;}
void dnt_cal(int e, int s) {seen[e][s] = 1;for(auto x : str) {if(x == 'N') e--;if(x == 'S') e++;if(x == 'W') s--;if(x == 'E') s++;seen[e][s] = 1;}}
/****************************************************************/
void init(int R, int C, int sr, int sc, int M, char *S)
{
int n = R;
int m = C;
for(int i = 0; i < M; i++) str.push_back(S[i]);
dnt_cal(sr, sc);
}
int colour(int ar, int ac, int br, int bc)
{
int ans = 0;
bool seen2[N][N] = {};
for(int i = ar; i <= br; i++)
{
for(int j = ac; j <= bc; j++)
{
if(seen2[i][j]) continue ;
if(seen[i][j]) continue;
int e = i;
int s = j;
int pe, ps;
//BFS:
queue<pair<int, int> > q;
q.push(make_pair(e,s));
while(!q.empty())
{
e = q.front().first;
s = q.front().second;
q.pop();
for(auto x : dx)
{
pe = x.first + e;
ps = x.second + s;
if(pe < ar or pe > br or ps < ac or ps > bc)
{
continue;
}
if(seen2[pe][ps])
{
continue;
}
if(seen[pe][ps])
{
continue;
}
seen2[pe][ps] = 1;
q.push(make_pair(pe,ps));
}
}
ans++;
}
}
return ans;
}