Submission #568473

#	Time	Username	Problem	Language	Result	Execution time	Memory
568473		mircea_007	T-Covering (eJOI19_covering)	C++17	100 / 100	48 ms	21028 KiB

covering

// 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 (stderr)

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] );
      |                                ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 30 / 30