| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1110353 | mychecksedad | Keys (IOI21_keys) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 800+10, K = 52, MX = 30;
struct Dsu {
vector<int> s, p;
int sz;
Dsu(int n){
sz = n;
s.resize(n+1, 1);
p.resize(n+1);
for(int i = 0; i <= n; ++i) p[i] = i;
}
int find(int v){
if(p[v] == v) return v;
return (p[v] = find(p[v]));
}
void merge(int a, int b){
a = find(a);
b = find(b);
if(a != b){
if(s[a] > s[b]) swap(a, b);
s[b] += s[a];
p[a] = b;
sz--;
}
}
};
vector<pii> g[N];
int m, r, c, C[N];
string s, t = "WENS";
vector<int> mask(16), to;
vector<int> BLOCK[N];
bool is_key[N], vis[N];
vector<vector<bool>> is(N, vector<bool>(16));
int f(int x, int y){
return x*c+y;
}
bool check(int x, int y){
return x >= 0 && y >= 0 && x < r && y < c;
}
int west(int x){
if(x % c == 0) return 0;
x--;
if(check(x / c, x % c)) return vis[x];
return 0;
}
int east(int x){
if(x % c == c - 1) return 0;
x++;
if(check(x / c, x % c)) return vis[x];
return 0;
}
int north(int x){
if(x / c == 0) return 0;
x -= c;
if(check(x / c, x % c)) return vis[x];
return 0;
}
int south(int x){
if(x / c == r - 1) return 0;
x += c;
if(check(x / c, x % c)) return vis[x];
return 0;
}
int search(int root, vector<int> &is_root, int finish){
vi used_vis;
queue<int> q;
q.push(root);
vis[root] = 1;
used_vis.pb(root);
int sz = 0;
while(q.size()){
int v = q.front(); q.pop();
++sz;
for(int k = 0; k < 4; ++k){
int u = to[k] + v;
if(vis[u] == 1) continue;
if(k == 0 && v % c == 0) continue;
if(k == 1 && v % c == c-1) continue;
if(k == 2 && v / c == 0) continue;
if(k == 3 && v / c == r-1) continue;
if(check(u / c, u % c)){
if(C[u] == 0) continue;
// cout << root << ' ' << u << '\n';
int msk = west(u) + east(u) * 2 + north(u) * 4 + south(u) * 8; //wens
// cout << msk << '\n';
if(mask[msk] >= C[u]){
vis[u] = 1;
used_vis.pb(u);
q.push(u);
if(finish && is_root[u]){
for(int &x: used_vis) vis[x] = 0;
return u;
}
}
}
}
}
for(int &x: used_vis) vis[x] = 0;
// cout << root << ' ' << sz << '\n';
if(finish == 0) return sz;
return -1;
}
void solve(){
cin >> m >> r >> c >> s;
vector<int> is_root(r*c, 1);
for(int i = 0; i < r; ++i){
for(int j = 0; j < c; ++j){
cin >> C[f(i, j)];
if(C[f(i, j)] == 0) is_root[f(i, j)] = 0;
}
}
to = vi{-1, +1, -c, +c};
s += s;
for(int msk = 0; msk < 16; ++msk){
int cur = 0, mx = 0;
for(int i = 0; i < s.length(); ++i){
bool in = 0;
if(s[i] == 'W' && (1&msk)) in = 1;
if(s[i] == 'E' && (2&msk)) in = 1;
if(s[i] == 'N' && (4&msk)) in = 1;
if(s[i] == 'S' && (8&msk)) in = 1;
if(in == 1) ++cur;
else mx=max(mx,cur), cur=0;
}
mask[msk] = max(mx,cur);
if(mask[msk] == 2*m) mask[msk] = MOD;
}
for(int i = 0; i < r*c; ++i) vis[i] = 0;
Dsu d(r*c);
bool OK = true;
while(OK){
OK = false;
vector<pii> P;
for(int i = 0; i < r*c; ++i){
if(is_root[i]){
auto p = search(i, is_root, 1);
if(p != -1) P.pb({i, p});
}
}
for(auto [u, v]: P){
if(d.find(u) != d.find(v)){
// cout << u << ' ' << v << '\n';
d.merge(u, v);
is_root[u] = false;
OK = true;
}
}
}
int sz = r*c;
vector<int> good(r*c), SZ(r*c);
for(int i = 0; i < r*c; ++i){
if(is_root[i]){
SZ[i] = search(i, is_root, 0);
sz = min(sz, SZ[i]);
good[d.find(i)] = 1;
}
}
int num = 0;
for(int i = 0; i < r*c; ++i){
if(is_root[i]){
if(SZ[i] == sz){
num += sz;
}
}
}
cout << sz << ' ' << num;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}