Submission #423282

#	Time	Username	Problem	Language	Result	Execution time	Memory
423282		JhonnyZaz	Race (IOI11_race)	C++14	100 / 100	1274 ms	51116 KiB

race

#include<bits/stdc++.h>

using namespace std;

const int INF = (int) 1e9;
const int N = 200100;

vector< pair< int, int > > tree[N];
vector< int > g[N];

int n, k, ans;

namespace decomposition {
  int cnt[N], depth[N], f[N]; 
  map< int, int > mp;
  vector< pair< int, int > > ve;

  int dfs (int u, int p = -1) {
    cnt[u] = 1;
    for (int v : g[u])
      if (!depth[v] && v != p)
        cnt[u] += dfs(v, u);
    return cnt[u];
  }
  int get_centroid (int u, int r, int p = -1) {
    for (int v : g[u])
      if (!depth[v] && v != p && cnt[v] > r)
        return get_centroid(v, r, u);
    return u;
  }

  void explore( int u, int p, int cost, int d )
  {
    if( cost > k ) return;
    ve.push_back( { cost, d } );

    for( auto e : tree[u] )
    {
      int v = e.first, w = e.second;
      if( !depth[v] && v != p )
        explore( v, u, cost + w, d + 1 );
    }
  }

  void solve( int centroid )
  {
    mp.clear();
    mp[0] = 0;

    for( auto e : tree[centroid] )
    {
      int v = e.first, w = e.second;

      if( !depth[v] )
      {
        ve.clear();
        explore( v, centroid, w, 1 );

        for( auto it : ve )
        {
          if( mp.count( k - it.first ) )
            ans = min( ans, mp[k-it.first] + it.second );
        }

        for( auto it : ve )
        {
          if( mp.count( it.first ) )
            mp[it.first] = min( mp[it.first], it.second );
          else
            mp[it.first] = it.second;
        }
      }

    }
  }

  int decompose (int u, int d = 1) {
    int centroid = get_centroid(u, dfs(u) >> 1);
    depth[centroid] = d; 

    solve( centroid );

    for (int v : g[centroid])
      if (!depth[v])
        f[decompose(v, d + 1)] = centroid;
    return centroid;
  }
  int lca (int u, int v) { 
    for (; u != v; u = f[u])
      if (depth[v] > depth[u])
        swap(u, v);
    return u;
  }
}


int best_path( int nn, int kk, int h[][2], int l[] )
{
  n = nn, k = kk, ans = INF;

  for( int e = 0; e < n - 1; ++ e )
  {
    int u = h[e][0], v = h[e][1], w = l[e];
    tree[u].push_back( { v, w } );
    tree[v].push_back( { u, w } );

    g[u].push_back( v );
    g[v].push_back( u );
  }

  decomposition::decompose( 0 );

  return ( ans == INF ? -1 : ans );
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57