oj.uz

Submission #1086176

# Submission time Handle Problem Language Result Execution time Memory
1086176 2024-09-09T16:43:14 Z contest_alt Dreaming (IOI13_dreaming) C++17
18 / 100
 27 ms 13148 KB 
#include "dreaming.h"

#include <stdio.h>
#include <vector>
#include <algorithm>

using ll = long long; // ??

namespace Solver {
  const int MAXN = 1e5;

  struct Edge {
    int u, cost;
    Edge( int u, int cost ): u(u), cost(cost) {}
  };

  std::vector<Edge> adj[MAXN];
  bool viz[MAXN];
  int dep[MAXN];

  void get_deps( int u, int p ) {
    viz[u] = true;

    dep[u] = 0;
    for( Edge e : adj[u] )
      if( e.u != p ){
        get_deps( e.u, u );
        dep[u] = std::max( dep[u], e.cost + dep[e.u] );
      }
  }

  int min_radius;
  void dai_tati( int u, int p, int up = 0 ) {
    //printf( "dep = %d | up = %d\n", dep[u], up );
    min_radius = std::min( min_radius, std::max( dep[u], up ) );

    int max1 = 0, max2 = 0;
    for( Edge e : adj[u] )
      if( e.u != p ){
        int chain = e.cost + dep[e.u];
        if( chain >= max1 ){
          max2 = max1;
          max1 = chain;
        }else if( chain >= max2 )
          max2 = chain;
      }

    for( Edge e : adj[u] )
      if( e.u != p ){
        int chain = e.cost + dep[e.u];
        dai_tati( e.u, u, e.cost + std::max( up, (max1 == chain) ? max2 : max1 ) );
      }
  }

  int rezolva_arbore( int root ) {
    get_deps( root, root ); // seteaza viz[] si gaseste adancimile

    min_radius = +1e9;
    dai_tati( root, root ); // eu prea lenes sa fac un singur dfs
    return min_radius;
  }

  int travelTime( int N, int M, int L, int A[], int B[], int T[] ){
    for( int i = 0; i < N; i++ ){
      viz[i] = false;
      adj[i].clear();
    }

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

    std::vector<int> comps;
    for( int i = 0; i < N; i++ )
      if( !viz[i] )
        comps.push_back( rezolva_arbore( i ) );

    // trebuie sa facem arbore partial de diametru minim cu comps[]
    std::sort( comps.begin(), comps.end(), std::greater<int>() );

    // sigur se poate max(comps[0] + L + comps[1], comps[1] + 2L + comps[2])
    // 0--1, 0--2, 0--3, ..., 0--(n-1)
    // NU SE POATE MAI BINE!
    // daca nu iei 0--1 esti doar prost
    // daca nu e muchie de la 0 la 2 => dist(0, 2) >= 2L deci minim comps[0] + 2L + comps[2] >= comps[1] + 2L + comps[2]
    // clar avem 0--1 si 0--2 => raspunsul este minim cel propus la inceput => acela e raspunsul

    // printf( "%d comps:", (int)comps.size() );
    // for( int x : comps )
    //   printf( " %d", x );
    // printf( "\n" );

    if( (int)comps.size() <= 1 )
      return comps.front();

    if( (int)comps.size() <= 2 )
      return comps[0] + L + comps[1];

    return std::max( comps[0] + L + comps[1], comps[1] + 2 * L + comps[2] );
  }
}


int travelTime( int N, int M, int L, int A[], int B[], int T[] ){
  return Solver::travelTime( N, M, L, A, B, T );
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 13148 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 12 ms 6492 KB Output is correct
2 Correct 13 ms 6364 KB Output is correct
3 Correct 12 ms 6368 KB Output is correct
4 Correct 13 ms 6364 KB Output is correct
5 Correct 13 ms 6316 KB Output is correct
6 Correct 15 ms 6624 KB Output is correct
7 Correct 14 ms 6492 KB Output is correct
8 Correct 14 ms 6376 KB Output is correct
9 Correct 12 ms 6456 KB Output is correct
10 Correct 17 ms 6408 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 4 ms 3940 KB Output is correct
13 Correct 3 ms 4056 KB Output is correct
14 Correct 3 ms 3800 KB Output is correct
15 Correct 4 ms 3848 KB Output is correct
16 Correct 4 ms 3944 KB Output is correct
17 Correct 4 ms 3800 KB Output is correct
18 Correct 4 ms 3800 KB Output is correct
19 Correct 4 ms 3912 KB Output is correct
20 Correct 1 ms 3420 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 3 ms 3932 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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