oj.uz

Submission #704673

# Submission time Handle Problem Language Result Execution time Memory
704673 2023-03-02T15:19:39 Z mircea_007 Dreaming (IOI13_dreaming) C++17
18 / 100
 51 ms 12340 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 12340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 12340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6360 KB Output is correct
2 Correct 18 ms 6364 KB Output is correct
3 Correct 23 ms 6344 KB Output is correct
4 Correct 20 ms 6328 KB Output is correct
5 Correct 27 ms 6232 KB Output is correct
6 Correct 28 ms 6560 KB Output is correct
7 Correct 24 ms 6548 KB Output is correct
8 Correct 21 ms 6224 KB Output is correct
9 Correct 17 ms 6228 KB Output is correct
10 Correct 31 ms 6488 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 4 ms 3796 KB Output is correct
13 Correct 7 ms 3796 KB Output is correct
14 Correct 7 ms 3796 KB Output is correct
15 Correct 6 ms 3796 KB Output is correct
16 Correct 7 ms 3796 KB Output is correct
17 Correct 4 ms 3796 KB Output is correct
18 Correct 4 ms 3804 KB Output is correct
19 Correct 4 ms 3796 KB Output is correct
20 Correct 2 ms 2656 KB Output is correct
21 Correct 2 ms 2644 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 6 ms 3840 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 12340 KB Output isn't correct
2 Halted 0 ms 0 KB -