#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 800 + 5;
const int logn = log2(maxn) + 1;
int lab[maxn * maxn];
int par[maxn * maxn];
bool ok[maxn][maxn];
int a[maxn][maxn];
int best[16];
int vis[maxn][maxn];
int n , m , k;
string s;
int dx[] = {-1 , 1 , 0 , 0};
int dy[] = {0 , 0 , -1 ,1};
int to2d(int x , int y){
return x * n + y;
}
bool valid(int x , int y){
if(x < 0 || y < 0 || x >= m || y >= n)return 0;
return a[x][y] > 0;
}
int FindLab(int u){
return lab[u] < 0 ? u : lab[u] = FindLab(lab[u]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen(taskname".INP","r")){
freopen(taskname".INP", "r",stdin);
freopen(taskname".OUT", "w",stdout);
}
{
cin >> k >> m >> n >> s;
for(auto & c : s){
if(c == 'N')c = 0;
else if(c == 'S')c = 1;
else if(c == 'W')c = 2;
else c = 3;
}
for(int i = 0 ; i < m ; ++i)for(int j = 0 ; j < n ; ++j)cin >> a[i][j];
}
{
for(int msk = 0 ; msk < 16 ; ++msk){
int j = -1;
for(int i = 0 ; i < 2 * k ; ++i){
if(msk & (1 << s[i % k]))best[msk] = max(best[msk] , i - j);
else j = i;
}
if(best[msk] >= k)best[msk] = 1e9;
}
}
{
int nTime = 0;
for(int i = 0 ; i < m * n ; ++i)lab[i] = -1 , par[i] = i;
bool flag = 0;
ii res = mp(1e9,0);
do{
flag = 0;
queue<ii> q;
for(int i = 0 ; i < m ; ++i){
for(int j = 0 ; j < n ; ++j){
if(a[i][j] > 0 && ok[i][j] == 0 && par[FindLab(to2d(i , j))] == to2d(i,j)){
int cur_lab = FindLab(to2d(i,j));
flag = 1;
while(q.size())q.pop();
q.push(mp(i,j));
vis[i][j] = ++nTime;
ii other = mp(-1 , -1);
int sum = 0;
while(q.size()){
auto u = q.front();q.pop();sum++;
for(int t = 0 ; t < 4 ; ++t){
int x = u.first + dx[t] , y = u.second + dy[t];
if(!valid(x , y) || vis[x][y] == nTime)continue;
int msk = 0;
for(int tt = 0 ; tt < 4 ; ++tt){
if(valid(x + dx[tt] , y + dy[tt]) && vis[x + dx[tt]][y + dy[tt]] == nTime){
msk |= (1 << tt);
}
}
if(best[msk] >= a[x][y]){
if(FindLab(to2d(x,y)) != cur_lab){
other = mp(x,y);
break;
}else{
q.push(mp(x,y));
vis[x][y] = nTime;
}
}
}
if(other != mp(-1,-1))break;
}
ok[i][j] = 1;
if(other == mp(-1,-1)){
if(res.first > sum)res = mp(sum,sum);
else if(res.first == sum)res.second += sum;
}else {
int tmp = FindLab(to2d(other.first,other.second));
int tmp1 = par[tmp];
if(ok[tmp1 / n][tmp1 % n] == 0){
if(lab[tmp] < lab[cur_lab]){
lab[tmp] += lab[cur_lab];
lab[cur_lab] = tmp;
}else{
lab[cur_lab] += lab[tmp];
lab[tmp] = cur_lab;
par[cur_lab] = tmp1;
}
}
}
}
}
}
}while(flag);
cout << res.first << " " << res.second << endl;
}
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:50:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".INP", "r",stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
virus.cpp:51:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(taskname".OUT", "w",stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
640 KB |
Output is correct |
2 |
Correct |
114 ms |
11128 KB |
Output is correct |
3 |
Correct |
142 ms |
11128 KB |
Output is correct |
4 |
Correct |
103 ms |
11256 KB |
Output is correct |
5 |
Correct |
144 ms |
11128 KB |
Output is correct |
6 |
Correct |
3 ms |
4864 KB |
Output is correct |
7 |
Correct |
192 ms |
11384 KB |
Output is correct |
8 |
Correct |
81 ms |
6136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
19 ms |
760 KB |
Output is correct |
3 |
Correct |
30 ms |
760 KB |
Output is correct |
4 |
Correct |
20 ms |
760 KB |
Output is correct |
5 |
Correct |
27 ms |
640 KB |
Output is correct |
6 |
Correct |
30 ms |
1016 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
28 ms |
1016 KB |
Output is correct |
9 |
Correct |
1 ms |
768 KB |
Output is correct |
10 |
Correct |
18 ms |
760 KB |
Output is correct |
11 |
Correct |
1 ms |
768 KB |
Output is correct |
12 |
Correct |
1 ms |
768 KB |
Output is correct |
13 |
Correct |
28 ms |
1016 KB |
Output is correct |
14 |
Correct |
27 ms |
1016 KB |
Output is correct |
15 |
Correct |
27 ms |
1016 KB |
Output is correct |
16 |
Correct |
29 ms |
1024 KB |
Output is correct |
17 |
Correct |
15 ms |
896 KB |
Output is correct |
18 |
Correct |
2 ms |
768 KB |
Output is correct |
19 |
Correct |
29 ms |
1016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
640 KB |
Output is correct |
2 |
Correct |
114 ms |
11128 KB |
Output is correct |
3 |
Correct |
142 ms |
11128 KB |
Output is correct |
4 |
Correct |
103 ms |
11256 KB |
Output is correct |
5 |
Correct |
144 ms |
11128 KB |
Output is correct |
6 |
Correct |
3 ms |
4864 KB |
Output is correct |
7 |
Correct |
192 ms |
11384 KB |
Output is correct |
8 |
Correct |
81 ms |
6136 KB |
Output is correct |
9 |
Correct |
1 ms |
384 KB |
Output is correct |
10 |
Correct |
19 ms |
760 KB |
Output is correct |
11 |
Correct |
30 ms |
760 KB |
Output is correct |
12 |
Correct |
20 ms |
760 KB |
Output is correct |
13 |
Correct |
27 ms |
640 KB |
Output is correct |
14 |
Correct |
30 ms |
1016 KB |
Output is correct |
15 |
Correct |
0 ms |
384 KB |
Output is correct |
16 |
Correct |
28 ms |
1016 KB |
Output is correct |
17 |
Correct |
1 ms |
768 KB |
Output is correct |
18 |
Correct |
18 ms |
760 KB |
Output is correct |
19 |
Correct |
1 ms |
768 KB |
Output is correct |
20 |
Correct |
1 ms |
768 KB |
Output is correct |
21 |
Correct |
28 ms |
1016 KB |
Output is correct |
22 |
Correct |
27 ms |
1016 KB |
Output is correct |
23 |
Correct |
27 ms |
1016 KB |
Output is correct |
24 |
Correct |
29 ms |
1024 KB |
Output is correct |
25 |
Correct |
15 ms |
896 KB |
Output is correct |
26 |
Correct |
2 ms |
768 KB |
Output is correct |
27 |
Correct |
29 ms |
1016 KB |
Output is correct |
28 |
Correct |
163 ms |
11376 KB |
Output is correct |
29 |
Correct |
98 ms |
11384 KB |
Output is correct |
30 |
Correct |
117 ms |
11384 KB |
Output is correct |
31 |
Correct |
157 ms |
11000 KB |
Output is correct |
32 |
Correct |
134 ms |
11000 KB |
Output is correct |
33 |
Correct |
102 ms |
11132 KB |
Output is correct |
34 |
Correct |
204 ms |
11320 KB |
Output is correct |
35 |
Correct |
115 ms |
8696 KB |
Output is correct |
36 |
Correct |
180 ms |
11128 KB |
Output is correct |
37 |
Correct |
157 ms |
11256 KB |
Output is correct |
38 |
Correct |
141 ms |
11128 KB |
Output is correct |
39 |
Correct |
155 ms |
11384 KB |
Output is correct |
40 |
Correct |
174 ms |
11384 KB |
Output is correct |
41 |
Correct |
85 ms |
11256 KB |
Output is correct |
42 |
Correct |
170 ms |
11000 KB |
Output is correct |
43 |
Correct |
129 ms |
11384 KB |
Output is correct |
44 |
Correct |
80 ms |
6136 KB |
Output is correct |