// This program was written on 19.05.2022
// for problem covering
// by Mircea Rebengiuc
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>// exit()
#include <vector>
#define MAXSIZE 1000000
#define INF 2000000000
static inline int max( int a, int b ){ return a > b ? a : b; }
static inline int min( int a, int b ){ return a < b ? a : b; }
int cost[MAXSIZE];
char is_special[MAXSIZE];
int comp[MAXSIZE];
int n, m;
int current_comp;
char delta[MAXSIZE];
int mincost[MAXSIZE];
int sum[MAXSIZE];
int dl[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };
int newid;
void dfs( int l, int c ){
char d, bias = is_special[l * m + c];
// comp[l][c] este setat din exterior
for( d = 0 ; d < 4 ; d++ ){
if( l + dl[d] >= 0 && l + dl[d] < n && c + dc[d] >= 0 && c + dc[d] < m ){
newid = (l + dl[d]) * m + c + dc[d];
if( !comp[newid] && (bias || is_special[newid]) ){
comp[newid] = current_comp;
dfs( l + dl[d], c + dc[d] );
}
}
}
}
static inline int fgetint(){
int n = 0, ch;
while( !isdigit( ch = fgetc( stdin ) ) );
do
n = n * 10 + ch - '0';
while( isdigit( ch = fgetc( stdin ) ) );
return n;
}
static inline void ragequit(){
printf( "No\n" );
exit( 0 );
}
static inline void assert( bool condition ){
if( !condition )
ragequit();
}
int main(){
int size, l, c, i, nspec, answer;
n = fgetint();
m = fgetint();
size = n * m;
for( i = 0 ; i < size ; i++ )
cost[i] = fgetint();
nspec = fgetint();
for( i = 0 ; i < nspec ; i++ ){
l = fgetint();
c = fgetint();
is_special[l * m + c] = 1;
}
// assing each cell to a conected component
current_comp = 1;
for( i = 0 ; i < size ; i++ )
if( is_special[i] && !comp[i] ){
mincost[comp[i] = current_comp] = +INF;
delta[current_comp] = sum[current_comp] = 0;
dfs( i / m, i % m );
current_comp++;
}
// calculate stats
for( i = 0 ; i < size ; i++ ){
if( (c = comp[i]) ){
sum[c] += cost[i];
if( is_special[i] ){
delta[c] -= 3;
}else{
delta[c]++;
mincost[c] = min( cost[i], mincost[c] );
}
}
}
answer = 0;
for( i = 1 ; i < current_comp ; i++ ){
assert( delta[i] >= 0 );
answer += sum[i];
if( delta[i] )
answer -= mincost[i];
}
printf( "%d\n", answer );
return 0;
}
Compilation message
covering.cpp: In function 'void dfs(int, int)':
covering.cpp:39:16: warning: array subscript has type 'char' [-Wchar-subscripts]
39 | if( l + dl[d] >= 0 && l + dl[d] < n && c + dc[d] >= 0 && c + dc[d] < m ){
| ^
covering.cpp:39:34: warning: array subscript has type 'char' [-Wchar-subscripts]
39 | if( l + dl[d] >= 0 && l + dl[d] < n && c + dc[d] >= 0 && c + dc[d] < m ){
| ^
covering.cpp:39:51: warning: array subscript has type 'char' [-Wchar-subscripts]
39 | if( l + dl[d] >= 0 && l + dl[d] < n && c + dc[d] >= 0 && c + dc[d] < m ){
| ^
covering.cpp:39:69: warning: array subscript has type 'char' [-Wchar-subscripts]
39 | if( l + dl[d] >= 0 && l + dl[d] < n && c + dc[d] >= 0 && c + dc[d] < m ){
| ^
covering.cpp:40:23: warning: array subscript has type 'char' [-Wchar-subscripts]
40 | newid = (l + dl[d]) * m + c + dc[d];
| ^
covering.cpp:40:40: warning: array subscript has type 'char' [-Wchar-subscripts]
40 | newid = (l + dl[d]) * m + c + dc[d];
| ^
covering.cpp:43:21: warning: array subscript has type 'char' [-Wchar-subscripts]
43 | dfs( l + dl[d], c + dc[d] );
| ^
covering.cpp:43:32: warning: array subscript has type 'char' [-Wchar-subscripts]
43 | dfs( l + dl[d], c + dc[d] );
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
680 KB |
Output is correct |
3 |
Correct |
3 ms |
1556 KB |
Output is correct |
4 |
Correct |
8 ms |
3976 KB |
Output is correct |
5 |
Correct |
25 ms |
12620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
4 ms |
1492 KB |
Output is correct |
4 |
Correct |
8 ms |
4012 KB |
Output is correct |
5 |
Correct |
25 ms |
12608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
564 KB |
Output is correct |
3 |
Correct |
3 ms |
1432 KB |
Output is correct |
4 |
Correct |
8 ms |
3996 KB |
Output is correct |
5 |
Correct |
25 ms |
12596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
596 KB |
Output is correct |
5 |
Correct |
3 ms |
1236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
292 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
680 KB |
Output is correct |
3 |
Correct |
3 ms |
1556 KB |
Output is correct |
4 |
Correct |
8 ms |
3976 KB |
Output is correct |
5 |
Correct |
25 ms |
12620 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
4 ms |
1492 KB |
Output is correct |
9 |
Correct |
8 ms |
4012 KB |
Output is correct |
10 |
Correct |
25 ms |
12608 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
564 KB |
Output is correct |
13 |
Correct |
3 ms |
1432 KB |
Output is correct |
14 |
Correct |
8 ms |
3996 KB |
Output is correct |
15 |
Correct |
25 ms |
12596 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
724 KB |
Output is correct |
19 |
Correct |
1 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
1236 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
2 ms |
596 KB |
Output is correct |
23 |
Correct |
3 ms |
1492 KB |
Output is correct |
24 |
Correct |
8 ms |
4052 KB |
Output is correct |
25 |
Correct |
28 ms |
12704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
680 KB |
Output is correct |
3 |
Correct |
3 ms |
1556 KB |
Output is correct |
4 |
Correct |
8 ms |
3976 KB |
Output is correct |
5 |
Correct |
25 ms |
12620 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
596 KB |
Output is correct |
8 |
Correct |
4 ms |
1492 KB |
Output is correct |
9 |
Correct |
8 ms |
4012 KB |
Output is correct |
10 |
Correct |
25 ms |
12608 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
564 KB |
Output is correct |
13 |
Correct |
3 ms |
1432 KB |
Output is correct |
14 |
Correct |
8 ms |
3996 KB |
Output is correct |
15 |
Correct |
25 ms |
12596 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
724 KB |
Output is correct |
19 |
Correct |
1 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
1236 KB |
Output is correct |
21 |
Correct |
0 ms |
292 KB |
Output is correct |
22 |
Correct |
1 ms |
296 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
1 ms |
292 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
2 ms |
596 KB |
Output is correct |
28 |
Correct |
3 ms |
1492 KB |
Output is correct |
29 |
Correct |
8 ms |
4052 KB |
Output is correct |
30 |
Correct |
28 ms |
12704 KB |
Output is correct |
31 |
Correct |
48 ms |
20464 KB |
Output is correct |
32 |
Correct |
25 ms |
11424 KB |
Output is correct |
33 |
Correct |
34 ms |
14192 KB |
Output is correct |
34 |
Correct |
27 ms |
10668 KB |
Output is correct |
35 |
Correct |
40 ms |
21028 KB |
Output is correct |