#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];
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;
memset(lab,-1,sizeof lab);
bool flag = 0;
ii res = mp(1e9,0);
do{
flag = 0;
for(int i = 0 ; i < m ; ++i){
for(int j = 0 ; j < n ; ++j){
if(a[i][j] > 0 && ok[i][j] == 0 && lab[to2d(i , j)] < 0){
flag = 1;
queue<ii> q;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)) != to2d(i,j)){
other = mp(x,y);
}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));
if(ok[tmp / n][tmp % n] == 0){
lab[tmp] += lab[to2d(i,j)];
lab[to2d(i,j)] = tmp;
}
}
}
}
}
}while(flag);
cout << res.first << " " << res.second << endl;
}
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:48: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:49: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);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
3200 KB |
Output is correct |
2 |
Correct |
213 ms |
9848 KB |
Output is correct |
3 |
Correct |
239 ms |
12152 KB |
Output is correct |
4 |
Correct |
205 ms |
9908 KB |
Output is correct |
5 |
Correct |
206 ms |
12280 KB |
Output is correct |
6 |
Correct |
5 ms |
7424 KB |
Output is correct |
7 |
Correct |
319 ms |
10104 KB |
Output is correct |
8 |
Correct |
124 ms |
8056 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2944 KB |
Output is correct |
2 |
Correct |
19 ms |
3200 KB |
Output is correct |
3 |
Correct |
29 ms |
3320 KB |
Output is correct |
4 |
Correct |
19 ms |
3200 KB |
Output is correct |
5 |
Correct |
29 ms |
3192 KB |
Output is correct |
6 |
Correct |
30 ms |
3584 KB |
Output is correct |
7 |
Correct |
2 ms |
2944 KB |
Output is correct |
8 |
Correct |
29 ms |
3576 KB |
Output is correct |
9 |
Correct |
3 ms |
3200 KB |
Output is correct |
10 |
Correct |
19 ms |
3200 KB |
Output is correct |
11 |
Correct |
3 ms |
3200 KB |
Output is correct |
12 |
Correct |
3 ms |
3200 KB |
Output is correct |
13 |
Correct |
29 ms |
3584 KB |
Output is correct |
14 |
Correct |
29 ms |
3584 KB |
Output is correct |
15 |
Correct |
28 ms |
3584 KB |
Output is correct |
16 |
Correct |
28 ms |
3556 KB |
Output is correct |
17 |
Correct |
16 ms |
3328 KB |
Output is correct |
18 |
Correct |
4 ms |
3200 KB |
Output is correct |
19 |
Correct |
30 ms |
3576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
3200 KB |
Output is correct |
2 |
Correct |
213 ms |
9848 KB |
Output is correct |
3 |
Correct |
239 ms |
12152 KB |
Output is correct |
4 |
Correct |
205 ms |
9908 KB |
Output is correct |
5 |
Correct |
206 ms |
12280 KB |
Output is correct |
6 |
Correct |
5 ms |
7424 KB |
Output is correct |
7 |
Correct |
319 ms |
10104 KB |
Output is correct |
8 |
Correct |
124 ms |
8056 KB |
Output is correct |
9 |
Correct |
2 ms |
2944 KB |
Output is correct |
10 |
Correct |
19 ms |
3200 KB |
Output is correct |
11 |
Correct |
29 ms |
3320 KB |
Output is correct |
12 |
Correct |
19 ms |
3200 KB |
Output is correct |
13 |
Correct |
29 ms |
3192 KB |
Output is correct |
14 |
Correct |
30 ms |
3584 KB |
Output is correct |
15 |
Correct |
2 ms |
2944 KB |
Output is correct |
16 |
Correct |
29 ms |
3576 KB |
Output is correct |
17 |
Correct |
3 ms |
3200 KB |
Output is correct |
18 |
Correct |
19 ms |
3200 KB |
Output is correct |
19 |
Correct |
3 ms |
3200 KB |
Output is correct |
20 |
Correct |
3 ms |
3200 KB |
Output is correct |
21 |
Correct |
29 ms |
3584 KB |
Output is correct |
22 |
Correct |
29 ms |
3584 KB |
Output is correct |
23 |
Correct |
28 ms |
3584 KB |
Output is correct |
24 |
Correct |
28 ms |
3556 KB |
Output is correct |
25 |
Correct |
16 ms |
3328 KB |
Output is correct |
26 |
Correct |
4 ms |
3200 KB |
Output is correct |
27 |
Correct |
30 ms |
3576 KB |
Output is correct |
28 |
Correct |
315 ms |
10104 KB |
Output is correct |
29 |
Correct |
293 ms |
10104 KB |
Output is correct |
30 |
Correct |
264 ms |
10232 KB |
Output is correct |
31 |
Correct |
293 ms |
10104 KB |
Output is correct |
32 |
Correct |
242 ms |
9720 KB |
Output is correct |
33 |
Correct |
216 ms |
9848 KB |
Output is correct |
34 |
Correct |
319 ms |
9996 KB |
Output is correct |
35 |
Correct |
202 ms |
8288 KB |
Output is correct |
36 |
Correct |
303 ms |
10236 KB |
Output is correct |
37 |
Correct |
270 ms |
10104 KB |
Output is correct |
38 |
Correct |
260 ms |
9848 KB |
Output is correct |
39 |
Correct |
316 ms |
11128 KB |
Output is correct |
40 |
Correct |
327 ms |
11128 KB |
Output is correct |
41 |
Correct |
191 ms |
9976 KB |
Output is correct |
42 |
Correct |
379 ms |
10120 KB |
Output is correct |
43 |
Correct |
276 ms |
10236 KB |
Output is correct |
44 |
Correct |
129 ms |
8056 KB |
Output is correct |