Submission #704673

#	Time	Username	Problem	Language	Result	Execution time	Memory
704673		mircea_007	Dreaming (IOI13_dreaming)	C++17	18 / 100	51 ms	12340 KiB

dreaming

#include "dreaming.h"

#include <vector>
#include <algorithm>

#include <stdio.h>

#define magic_sauce inline __attribute__((always_inline))

magic_sauce int min( int a, int b ){ return a < b ? a : b; }
magic_sauce int max( int a, int b ){ return a > b ? a : b; }

const int MAXN = 1e5;

struct Edge { int v, c; };
std::vector<Edge> adj[MAXN];
int viz[MAXN];
int down[MAXN];

void gen_down( int u, int p ){
  down[u] = 0;
  for( Edge e : adj[u] )
    if( e.v != p ){
      gen_down( e.v, u );
      down[u] = max( down[u], down[e.v] + e.c );
    }
}

bool seen_best; // ca sa nu stea pe stiva

int dmax( int u, int p, int up ){
  int ret = max( up, down[u] ), otherwise = up;
  
  viz[u] = true;

  for( Edge e : adj[u] )
    if( e.v != p )
      up = max( up, down[e.v] + e.c );

  seen_best = false;
  for( Edge e : adj[u] )
    if( e.v != p ){
      if( (down[e.v] + e.c != up) || seen_best )
        otherwise = max( otherwise, down[e.v] + e.c );
      else
        seen_best = true;
    }

  for( Edge e : adj[u] )
    if( e.v != p )
      ret = min( ret, dmax( e.v, u, (e.c + down[e.v] == up ? otherwise : up) + e.c ) );

  return ret;
}

int tcomp[MAXN];
int nc;

int travelTime( int N, int M, int L, int A[], int B[], int T[] ){
  int i, j, jj;

  for( i = 0 ; i < N ; i++ ){
    viz[i] = false;
    adj[i].clear();
  }

  for( i = 0 ; i < M ; i++ ){
    adj[A[i]].push_back( Edge{ B[i], T[i] } );
    adj[B[i]].push_back( Edge{ A[i], T[i] } );
  }

  nc = 0;
  for( i = 0 ; i < N ; i++ )
    if( !viz[i] ){
      gen_down( i, i );
      tcomp[nc++] = dmax( i, i, 0 );
    }

  std::sort( tcomp, tcomp + nc, []( int a, int b ){ return a > b; } );

  if( nc == 1 )
    return tcomp[0];

  if( nc == 2 )
    return tcomp[0] + tcomp[1] + L;

  return max( tcomp[0] + tcomp[1] + L, tcomp[1] + tcomp[2] + (L << 1) );
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:60:10: warning: unused variable 'j' [-Wunused-variable]
   60 |   int i, j, jj;
      |          ^
dreaming.cpp:60:13: warning: unused variable 'jj' [-Wunused-variable]
   60 |   int i, j, jj;
      |             ^~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23