// ~ Be Name Khoda ~ //
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn3 = 810;
const int mod = 1e9 + 7;
const ll inf = 1e18;
/*
* 0 *
1 X 2
* 3 *
*/
char c[4] = {'N', 'W', 'E', 'S'};
pair <int, int> adj[4] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
int mx[100], mark[maxn], cmp[maxn3][maxn3];
int a[maxn3][maxn3], n, m;
vector <pair<int, int>> ed[maxn], eversaw[maxn], av[maxn];
bool Run = false;
bool ok(int i, int j){
return min(i, j) >= 0 && i < n && j < m && a[i][j];
}
bool check_ed(int x, int y, int a){
if(cmp[x][y] == a)
return false;
int mask = 0;
for(int i = 0; i < 4; i++)
if(ok(x - adj[i].fi, y - adj[i].se) && cmp[x - adj[i].fi][y - adj[i].se] == a)
mask += (1 << i);
return mx[mask] >= (::a[x][y]);
}
int merge(int a, int b){
if(a == b)
return a;
if(av[a].size() < av[b].size())
swap(a, b);
for(auto [u, v] : av[b]){
av[a].pb({u, v});
cmp[u][v] = a;
}
for(auto [u, v] : av[b]) for(int i = 0; i < 4; i++)
if(ok(u + adj[i].fi, v + adj[i].se) && check_ed(u + adj[i].fi, v + adj[i].se, a))
ed[a].pb({u + adj[i].fi, v + adj[i].se});
for(auto p : ed[b]){
//cout << "it's " << p.fi << ' ' << p.se << endl;
ed[a].pb(p);
}
for(auto p : eversaw[b])
eversaw[a].pb(p);
av[b].clear();
eversaw[b].clear();
ed[b].clear();
av[b].shrink_to_fit();
eversaw[b].shrink_to_fit();
ed[b].shrink_to_fit();
//cout << "here merge of " << a << ' ' << b << endl;
return a;
}
bool dfs(int v){
mark[v] = 1;
while(ed[v].size()){
int u = cmp[ed[v].back().fi][ed[v].back().se];
pair <int, int> tmp = ed[v].back();
//cout << v << ' ' << u << ' ' << mark[u] << ' ' << ed[v].back().fi << ' ' << ed[v].back().se << endl;
if(u == v){
ed[v].pop_back();
continue;
}
eversaw[v].pb(ed[v].back());
ed[v].pop_back();
if(!mark[u]){
if(dfs(u)){
if(eversaw[v].empty())
exit(0);
v = merge(cmp[tmp.fi][tmp.se], v);
}
mark[v] = 1;
}
else if(mark[u] == 1){
ed[v].pb(tmp);
//cout << ed[v].back().fi << ' ' << ed[v].back().se << endl;
//cout << "ha? " << v << ' ' << eversaw[v].size() << ' ' << eversaw[v].back().fi << ' ' << eversaw[v].back().se << endl;
return true;
}
}
mark[v] = 2;
return false;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> n >> m;
Run |= max(n, m) <= 50;
string s; cin >> s;
bool okk = true;
for(int i = 0; i < s.size(); i++)
okk &= (s[i] == 'W' || s[i] == 'E');
Run |= okk;
Run ^= 1;
string t = s;
while(t.size() < 200000)
t = t + s;
s = t;
for(int mask = 1; mask < (1 << 4); mask++){
int last = 0;
char av[4];
for(int i = 0; i < 4; i++){
if((mask >> i)&1)
av[i] = c[i];
else
av[i] = 'X';
}
for(int i = 0; i < s.size(); i++){
if(s[i] != av[0] && s[i] != av[1] && s[i] != av[2] && s[i] != av[3])
last = i + 1;
else
mx[mask] = max(mx[mask], i - last + 1);
}
}
//cout << mx[4] << endl;
int l = 0, r = 0;
int pt = 0;
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++)
cin >> a[i][j];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++){
if(!a[i][j])
continue;
cmp[i][j] = pt;
av[pt].pb({i, j});
for(int x = 0; x < 4; x++)
if(ok(i + adj[x].fi, j + adj[x].se) && mx[(1 << x)] >= a[i + adj[x].fi][j + adj[x].se]){
ed[pt].pb({i + adj[x].fi, j + adj[x].se});
}
//cout << i << ' ' << j << ' ' << cmp[i][j] << ' ' << ed[pt].size() << endl;
pt++;
}
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(!mark[cmp[i][j]])
dfs(cmp[i][j]);
int mn = n * m + 1, cnt = 0;
memset(mark, false, sizeof mark);
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(!mark[cmp[i][j]]){
int re = true;
mark[cmp[i][j]] = true;
for(auto [u, v] : eversaw[cmp[i][j]]) if(cmp[u][v] != cmp[i][j]){
//cout << i << ' ' << j << ' ' << cmp[i][j] << ' ' << u << ' ' << v << ' ' << cmp[u][v] << endl;
re = false;
}
if(re){
int val = av[cmp[i][j]].size();
//cout << i << ' ' << j << ' ' << cmp[i][j] << ' ' << val << endl;
if(val < mn){
mn = val;
cnt = val;
}
else if(val == mn)
cnt += val;
}
}
cout << mn << endl << cnt << endl;
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i = 0; i < s.size(); i++)
| ~~^~~~~~~~~~
virus.cpp:136:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int i = 0; i < s.size(); i++){
| ~~^~~~~~~~~~
virus.cpp:144:9: warning: unused variable 'l' [-Wunused-variable]
144 | int l = 0, r = 0;
| ^
virus.cpp:144:16: warning: unused variable 'r' [-Wunused-variable]
144 | int l = 0, r = 0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
75276 KB |
Output is correct |
| 2 |
Correct |
499 ms |
122708 KB |
Output is correct |
| 3 |
Correct |
425 ms |
140292 KB |
Output is correct |
| 4 |
Correct |
198 ms |
140180 KB |
Output is correct |
| 5 |
Correct |
116 ms |
100212 KB |
Output is correct |
| 6 |
Correct |
298 ms |
80024 KB |
Output is correct |
| 7 |
Correct |
226 ms |
120212 KB |
Output is correct |
| 8 |
Correct |
76 ms |
85244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
303 ms |
75368 KB |
Output is correct |
| 2 |
Correct |
38 ms |
75152 KB |
Output is correct |
| 3 |
Incorrect |
50 ms |
75256 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
75276 KB |
Output is correct |
| 2 |
Correct |
499 ms |
122708 KB |
Output is correct |
| 3 |
Correct |
425 ms |
140292 KB |
Output is correct |
| 4 |
Correct |
198 ms |
140180 KB |
Output is correct |
| 5 |
Correct |
116 ms |
100212 KB |
Output is correct |
| 6 |
Correct |
298 ms |
80024 KB |
Output is correct |
| 7 |
Correct |
226 ms |
120212 KB |
Output is correct |
| 8 |
Correct |
76 ms |
85244 KB |
Output is correct |
| 9 |
Correct |
303 ms |
75368 KB |
Output is correct |
| 10 |
Correct |
38 ms |
75152 KB |
Output is correct |
| 11 |
Incorrect |
50 ms |
75256 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
