Submission #1107452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107452		mircea_007	Dreaming (IOI13_dreaming)	C++17	100 / 100	59 ms	18268 KiB

dreaming

#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;
  int diameter;
  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;
      }

    diameter = std::max( diameter, max1 + max2 );

    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 ) );
      }
  }

  // raza, diametru
  std::pair<int, int> rezolva_arbore( int root ) {
    get_deps( root, root ); // seteaza viz[] si gaseste adancimile

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

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

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

        biggest_d = std::max( biggest_d, comp.second );
      }

    // 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 std::max( biggest_d, comps.front() );

    if( (int)comps.size() <= 2 )
      return std::max( biggest_d, comps[0] + L + comps[1] );

    return std::max( biggest_d, 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: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23