#define DEBUG 0
#include <bits/stdc++.h>
using namespace std;
#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}
// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
public:
template<typename T>
_Debug& operator,(T val) {
cout << val << endl;
return *this;
}
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif
// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back
// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;
// ---------- END OF TEMPLATE ----------
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
char D[200000];
int U[800][800];
int tt[16];
int parent[640000];
int find(int n) {
if (parent[n] != n) parent[n] = find(parent[n]);
return parent[n];
}
int done[640000];
queue<pii> Q;
int visited[800][800];
int main() {
int i,j;
int M,R,C;
scanf("%d %d %d",&M,&R,&C);
for (i = 0; i < M; i++) scanf(" %c",&D[i]),D[i+M] = D[i];
for (i = 0; i < R; i++) {
for (j = 0; j < C; j++) scanf("%d",&U[i][j]);
}
for (i = 1; i < 16; i++) {
int p = -1;
for (j = 0; j < 2*M; j++) {
int yes;
if (D[j] == 'W') yes = (i & 1);
else if (D[j] == 'N') yes = (i & 2);
else if (D[j] == 'E') yes = (i & 4);
else yes = (i & 8);
if (yes) tt[i] = max(tt[i],j-p);
else p = j;
}
if (tt[i] >= M) tt[i] = 100001;
}
int k,l,f = 1,t = 0;
int best = R*C+1,num = 1;
for (i = 0; i < R*C; i++) parent[i] = i;
while (f) {
f = 0;
for (i = 0; i < R; i++) {
for (j = 0; j < C; j++) {
if ((U[i][j] > 0) && !done[i*C+j] && (find(i*C+j) == i*C+j)) {
int c = 0,mx = -1,my = -1;
visited[i][j] = ++t,Q.push(mp(i,j));
while (!Q.empty()) {
int x = Q.front().second,y = Q.front().first;
Q.pop(),c++;
for (k = 0; k < 4; k++) {
int xx = x+dx[k],yy = y+dy[k];
if ((xx >= 0) && (xx < C) && (yy >= 0) && (yy < R) && (visited[yy][xx] != t) && (U[yy][xx] > 0)) {
int m = 0;
for (l = 0; l < 4; l++) {
int x2 = xx+dx[l],y2 = yy+dy[l];
if ((x2 >= 0) && (x2 < C) && (y2 >= 0) && (y2 < R) && (visited[y2][x2] == t)) m |= (1 << l);
}
if (tt[m] >= U[yy][xx]) {
if (find(yy*C+xx) != i*C+j) mx = xx,my = yy;
visited[yy][xx] = t;
Q.push(mp(yy,xx));
}
}
}
if (mx != -1) break;
}
while (!Q.empty()) Q.pop();
if (mx == -1) {
if (c < best) best = num = c;
else if (c == best) num += c;
done[i*C+j] = 1;
}
else if (done[find(my*C+mx)]) done[i*C+j] = 1;
else parent[i*C+j] = find(my*C+mx);
f = 1;
}
}
}
}
printf("%d\n%d\n",best,num);
return 0;
}
Compilation message
virus.cpp: In function 'int main()':
virus.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&M,&R,&C);
~~~~~^~~~~~~~~~~~~~~~~~~~~
virus.cpp:75:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i = 0; i < M; i++) scanf(" %c",&D[i]),D[i+M] = D[i];
~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
virus.cpp:77:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (j = 0; j < C; j++) scanf("%d",&U[i][j]);
~~~~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
476 KB |
Output is correct |
2 |
Correct |
143 ms |
10268 KB |
Output is correct |
3 |
Correct |
165 ms |
10324 KB |
Output is correct |
4 |
Correct |
130 ms |
10360 KB |
Output is correct |
5 |
Correct |
158 ms |
10400 KB |
Output is correct |
6 |
Correct |
5 ms |
4216 KB |
Output is correct |
7 |
Correct |
212 ms |
10580 KB |
Output is correct |
8 |
Correct |
85 ms |
5612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
12 ms |
608 KB |
Output is correct |
3 |
Correct |
32 ms |
632 KB |
Output is correct |
4 |
Correct |
12 ms |
632 KB |
Output is correct |
5 |
Correct |
32 ms |
572 KB |
Output is correct |
6 |
Correct |
33 ms |
888 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
32 ms |
860 KB |
Output is correct |
9 |
Correct |
3 ms |
632 KB |
Output is correct |
10 |
Correct |
13 ms |
608 KB |
Output is correct |
11 |
Correct |
3 ms |
632 KB |
Output is correct |
12 |
Correct |
3 ms |
636 KB |
Output is correct |
13 |
Correct |
33 ms |
888 KB |
Output is correct |
14 |
Correct |
34 ms |
860 KB |
Output is correct |
15 |
Correct |
33 ms |
852 KB |
Output is correct |
16 |
Correct |
29 ms |
892 KB |
Output is correct |
17 |
Correct |
18 ms |
808 KB |
Output is correct |
18 |
Correct |
4 ms |
808 KB |
Output is correct |
19 |
Correct |
33 ms |
856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
476 KB |
Output is correct |
2 |
Correct |
143 ms |
10268 KB |
Output is correct |
3 |
Correct |
165 ms |
10324 KB |
Output is correct |
4 |
Correct |
130 ms |
10360 KB |
Output is correct |
5 |
Correct |
158 ms |
10400 KB |
Output is correct |
6 |
Correct |
5 ms |
4216 KB |
Output is correct |
7 |
Correct |
212 ms |
10580 KB |
Output is correct |
8 |
Correct |
85 ms |
5612 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
12 ms |
608 KB |
Output is correct |
11 |
Correct |
32 ms |
632 KB |
Output is correct |
12 |
Correct |
12 ms |
632 KB |
Output is correct |
13 |
Correct |
32 ms |
572 KB |
Output is correct |
14 |
Correct |
33 ms |
888 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
32 ms |
860 KB |
Output is correct |
17 |
Correct |
3 ms |
632 KB |
Output is correct |
18 |
Correct |
13 ms |
608 KB |
Output is correct |
19 |
Correct |
3 ms |
632 KB |
Output is correct |
20 |
Correct |
3 ms |
636 KB |
Output is correct |
21 |
Correct |
33 ms |
888 KB |
Output is correct |
22 |
Correct |
34 ms |
860 KB |
Output is correct |
23 |
Correct |
33 ms |
852 KB |
Output is correct |
24 |
Correct |
29 ms |
892 KB |
Output is correct |
25 |
Correct |
18 ms |
808 KB |
Output is correct |
26 |
Correct |
4 ms |
808 KB |
Output is correct |
27 |
Correct |
33 ms |
856 KB |
Output is correct |
28 |
Correct |
227 ms |
8076 KB |
Output is correct |
29 |
Correct |
215 ms |
8096 KB |
Output is correct |
30 |
Correct |
198 ms |
8084 KB |
Output is correct |
31 |
Correct |
211 ms |
8704 KB |
Output is correct |
32 |
Correct |
180 ms |
8664 KB |
Output is correct |
33 |
Correct |
141 ms |
10292 KB |
Output is correct |
34 |
Correct |
263 ms |
7888 KB |
Output is correct |
35 |
Correct |
155 ms |
6088 KB |
Output is correct |
36 |
Correct |
228 ms |
9720 KB |
Output is correct |
37 |
Correct |
216 ms |
7788 KB |
Output is correct |
38 |
Correct |
192 ms |
7800 KB |
Output is correct |
39 |
Correct |
203 ms |
10616 KB |
Output is correct |
40 |
Correct |
221 ms |
10460 KB |
Output is correct |
41 |
Correct |
134 ms |
10352 KB |
Output is correct |
42 |
Correct |
200 ms |
10104 KB |
Output is correct |
43 |
Correct |
198 ms |
10360 KB |
Output is correct |
44 |
Correct |
91 ms |
5624 KB |
Output is correct |