#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
int n, m;
bool in_range(int i, int j){ return 0 < i && i <= n && 0 < j && j <= m; }
struct dsu{
vector<int> rep, sz, on_stack, wrong;
void init(int N){
rep.resize(N+1), sz.resize(N+1), on_stack.resize(N+1, 0), wrong.resize(N+1, 0);
for(int i = 1; i <= N; ++i) rep[i] = i, sz[i] = 1;
}
int Find(int x){
if(x != rep[x]) rep[x] = Find(rep[x]);
return rep[x];
}
void Union(int a, int b){ // nie muszę chyba przekazywać wrong w unionie, bo nigdy nie połączę ze złą spójną
a = Find(a), b = Find(b);
if(a == b) return;
if(sz[a] < sz[b]) swap(a, b);
rep[b] = a, sz[a] += sz[b], on_stack[a] += on_stack[b];
}
};
void answer(){
int k; scanf("%d%d%d", &k, &n, &m);
char c = char(getchar_unlocked());
unordered_map<char, int> mp; mp['N'] = 0, mp['E'] = 1, mp['S'] = 2, mp['W'] = 3;
vector<int> h(k<<1);
for(int i = 0; i < k; ++i) c = char(getchar_unlocked()), h[i] = mp[c], h[i+k] = mp[c];
//~ for(int i = 0; i < k*2; ++i) printf("%d ", h[i]);
//~ pn;
vector<int> dp(16, 0); dp[0] = 0, dp[15] = inf;
for(int msk = 1; msk < 15; ++msk){
int len = 0;
for(int i = 0; i < k*2; ++i){
if(msk&(1<<h[i])) ++len;
else dp[msk] = max(dp[msk], len), len = 0;
}
dp[msk] = max(dp[msk], len);
if(dp[msk] == k*2) dp[msk] = inf;
//~ printf("%d\n", dp[msk]);
}
vv<vv<int>> t(n+2, vv<int>(m+2, 0)), id(n+2, vv<int>(m+2, 0));
vector<pii> pos(n*m+1);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) scanf("%d", &t[i][j]), id[i][j] = (i-1)*m+j, pos[(i-1)*m+j] = pii(i, j);
dsu dsu; dsu.init(n*m);
vector<int> st_dfs, st_rep, neigh(n*m+1, 0), vis(n*m+1, 0);
vector<pii> dir(4); dir[0] = pii(-1, 0), dir[1] = pii(0, 1), dir[2] = pii(1, 0), dir[3] = pii(0, -1);
for(int sty = 1; sty <= n; ++sty) for(int stx = 1; stx <= m; ++stx) if(t[sty][stx] && !vis[id[sty][stx]]){ // todo : pamietac, ze nie mozna wchodzic na te gdzie jest 0, sprawdzac, czy w on_stack jest find
st_dfs.emplace_back(id[sty][stx]), st_rep.emplace_back(id[sty][stx]);
dsu.on_stack[id[sty][stx]] = 1, vis[id[sty][stx]] = 1;
while(!st_dfs.empty()){
//~ for(int u : st_dfs) printf("%d ", u);
//~ pn;
//~ for(int u : st_rep) printf("%d ", u);
//~ pn; pn;
int x = st_dfs.back(), tt = dsu.rep[x];
if(tt != dsu.Find(x)) neigh[x] = 0;
if(neigh[x] > 3){
st_dfs.pop_back(), --dsu.on_stack[dsu.Find(x)];
if(!dsu.on_stack[dsu.Find(x)]) st_rep.pop_back();
continue;
}
pii posx = pos[x], posu = pii(posx.fi+dir[neigh[x]].fi, posx.se+dir[neigh[x]].se);
//~ printf("%d %d: %d\n", posx.fi, posx.se, dsu.Find(x));
++neigh[x]; // todo: pamietac, by zwiekszac counter sasiada ++neigh[x]
if(!t[posu.fi][posu.se] || !in_range(posu.fi, posu.se)) continue;
int u = id[posu.fi][posu.se];
//~ tutaj chce wstawic jeszcze, czy da sie w ogole przejsc do goscia
int msk = 0;
for(int i = 0; i < 4; ++i)
if(in_range(posu.fi+dir[i].fi, posu.se+dir[i].se) && dsu.Find(id[posu.fi+dir[i].fi][posu.se+dir[i].se]) == dsu.Find(x)) msk |= 1<<i;
if(dp[msk] < t[posu.fi][posu.se]) continue;
if(!vis[u]){
st_dfs.emplace_back(u), st_rep.emplace_back(u);
dsu.on_stack[u] = 1, vis[u] = 1;
}
else if(dsu.on_stack[dsu.Find(u)]){
int sp = dsu.Find(u); // tutaj jakis assercik czy nie jest pusty, ale nie powinien
if(dsu.Find(x) != sp) neigh[x] = 0;
while(st_rep.back() != sp) dsu.Union(st_rep.back(), sp), st_rep.pop_back();
st_rep.pop_back(), st_rep.emplace_back(dsu.Find(u));
}
else{
int sp = dsu.Find(x); dsu.wrong[sp] = 1;
while(!st_dfs.empty() && dsu.Find(st_dfs.back()) == sp) st_dfs.pop_back();
st_rep.pop_back(), dsu.on_stack[sp] = 0;
}
}
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) if(!t[i][j]) dsu.wrong[id[i][j]] = 1;
int result = inf, cnt = 0;
for(int i = 1, a; i <= n*m; ++i){
a = dsu.Find(i);
//~ printf("%d: %d\n", i, a);
if(!dsu.wrong[a]){
if(dsu.sz[a] < result) result = dsu.sz[a], cnt = 1;
else if(dsu.sz[a] == result) ++cnt;
}
dsu.wrong[a] = 1;
}
printf("%d\n%d\n", result, result*cnt);
}
int main(){
int T = 1;
for(++T; --T; ) answer();
return 0;
}
Compilation message
virus.cpp: In function 'void answer()':
virus.cpp:33:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | int k; scanf("%d%d%d", &k, &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
virus.cpp:55:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | for(int j = 1; j <= m; ++j) scanf("%d", &t[i][j]), id[i][j] = (i-1)*m+j, pos[(i-1)*m+j] = pii(i, j);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
860 KB |
Output is correct |
| 2 |
Incorrect |
122 ms |
26768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
860 KB |
Output is correct |
| 2 |
Incorrect |
122 ms |
26768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
