Submission #788711

#	Time	Username	Problem	Language	Result	Execution time	Memory
788711		vjudge1	Race (IOI11_race)	C++17	100 / 100	428 ms	104700 KiB

race

#include "bits/stdc++.h"

using namespace std;

#define ll long long
#define ii pair<int,int>
const int ms = 2e5 + 10;


ll h[ms], dis[ms], ans, k, n;
vector<ii> g[ms];
map<ll, ll > mp[ms];


void dfs(int u=0, int p=-1, ll d=0, int height =0){
  mp[u][d]= height;
  h[u] = height;
  dis[u] = d;
  for(auto [v, w] : g[u]){
    if(v == p) continue;
    dfs(v, u, d+w, height+1);
  }
}

void sack(int u=0, int p=-1){
  // dis[u] + target = k
  // x + y - (2 * dis[u]) = k
  // x + y = 2*dis[u] + k
  // y = 2*dis[u] + k - x

  for(auto [v, w] : g[u]){
    if(v == p) continue;
    sack(v, u);
    if(mp[v].size() > mp[u].size()) mp[u].swap(mp[v]);
    for(auto [x, y] : mp[v]){
      if(mp[u].find(2ll*dis[u] + k - x) != mp[u].end()){
        ll now = y + mp[u][2*dis[u] + k - x] - 2*h[u];
        if(ans == -1  || ans > now) ans = now;
      }
    }

    for(auto [x, y] : mp[v]){
      if(mp[u].find(x) != mp[u].end()){
        mp[u][x] = min(mp[u][x], y);
      }
      else mp[u][x] = y;
    }
  }
}

int best_path(int N, int K, int H[][2], int L[]){
  k = K;
  n = N;
  for(int i=0; i<n-1; i++){
    g[H[i][0]].push_back({H[i][1], L[i]});
    g[H[i][1]].push_back({H[i][0], L[i]});
  }

  ans = -1;
  dfs();
  sack();
  return ans;
}

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