Submission #1100013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100013		ardadut	Race (IOI11_race)	C++17	100 / 100	271 ms	38228 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

vector<pair<ll,ll>> adj[200005];
bool del[200005];
ll sub[200005];
ll dp[1000000];
ll k;
ll ans = 1e10;

inline ll get_sub(ll node, ll parent){
  sub[node] = 1;
  for(auto go : adj[node]){
    if(go.first == parent or del[go.first]) continue;
    sub[node] += get_sub(go.first,node);
  }
  return sub[node];
}

inline ll get_centroid(ll node, ll parent, ll tree_size){
  for(auto go : adj[node]){
    if(go.first == parent or del[go.first]) continue;
    if(sub[go.first] >= tree_size/2) return get_centroid(go.first,node,tree_size);
  }
  return node;
}

inline void control(ll node, ll parent, ll val, ll edge){
  if(val > k) return;
  if(dp[k-val] != -1) ans = min(ans,dp[k-val] + edge);
  for(auto go : adj[node]){
    if(go.first == parent or del[go.first]) continue;
    control(go.first,node,val+go.second,edge+1);
  }
  
}

inline void build(ll node, ll parent, ll val, ll edge){
  if(val > k) return;
  if(dp[val] != -1) dp[val] = min(dp[val],edge);
  else dp[val] = edge;
  for(auto go : adj[node]){
    if(go.first == parent or del[go.first]) continue;
    build(go.first,node,val+go.second,edge+1);
  }
}

inline void dp_reset(ll node, ll parent, ll val){
  if(val > k) return;
  dp[val] = -1;
  for(auto go : adj[node]){
    if(go.first == parent or del[go.first]) continue;
    dp_reset(go.first,node,val+go.second);
  }
}

inline void solve(ll node){
  ll centroid = get_centroid(node,-1,get_sub(node,-1));
  dp[0] = 0;
  for(auto go : adj[centroid]){
    if(del[go.first]) continue;
    control(go.first,centroid,go.second,1);
    build(go.first,centroid,go.second,1);
  }

  for(auto go : adj[centroid]){
    if(del[go.first]) continue;
    dp_reset(go.first,centroid,go.second);
  }

  del[centroid] = 1;

  for(auto go : adj[centroid]){
    if(del[go.first]) continue;
    solve(go.first);
  }

}

int best_path(int N, int K, int H[][2], int L[]){
  k = K;
  memset(dp,-1,sizeof(dp));
  for(ll i = 0 ; i < N-1 ; i++){
    adj[H[i][1]].pb({H[i][0],L[i]});
    adj[H[i][0]].pb({H[i][1],L[i]});
  }

  solve(0);

  if(ans == 1e10) ans = -1;

  return ans;
}

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