Submission #1150125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150125		ThylOne	Race (IOI11_race)	C++20	100 / 100	515 ms	48184 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

struct edge{
  int neigh;
  int weight;
};

const int maxiN = 2e5;
vector<edge> links[maxiN];
bool erased[maxiN];
int sz[maxiN];

void compute_sz(int node, int papa=-1){
  sz[node] = 1;
  for(auto e:links[node])if(papa != e.neigh && !erased[e.neigh]){
    compute_sz(e.neigh,node);
    sz[node] += sz[e.neigh];
  }
}
int get_centroid(int node, int size_c, int papa=-1){
  for(auto &e: links[node])
    if(!erased[e.neigh] && sz[e.neigh]*2>size_c && papa != e.neigh)
      return get_centroid(e.neigh, size_c,node);
  return node;
}

void dfs(int node, int papa, int depth,int weight,vector<pair<int,int>> &dw){
  dw.push_back(make_pair(weight, depth));
  for(auto &e:links[node])if(e.neigh != papa && !erased[e.neigh])
    dfs(e.neigh,node,depth+1,weight+e.weight,dw);
}
int ans = 2*maxiN;
void centroid_decomposition(int node, int k){
  compute_sz(node);
  int X = get_centroid(node, sz[node]);

  unordered_map<int, int> mem;
  mem[0]=0;

  for(auto e:links[X])if(!erased[e.neigh]){
    vector<pair<int,int>> wd;
    dfs(e.neigh, X, 1,e.weight, wd);
    for(auto &[w,d]:wd)
      if(mem.count(k-w))
        ans = min(ans, d + mem[k - w]);

    for(auto &[w,d]:wd){
      if(mem.count(w))
        mem[w] = min(mem[w], d);
      else
        mem[w] = d;
    }
  }
  
  erased[X] = true;
  for(auto &e:links[X])if(!erased[e.neigh])
    centroid_decomposition(e.neigh, k);
}
int best_path(int N, int K, int H[][2], int L[])
{
  for(int i = 0 ; i < N - 1 ; i++){
    links[H[i][1]].push_back({H[i][0], L[i]});
    links[H[i][0]].push_back({H[i][1], L[i]});
  }
  centroid_decomposition(0, K);
  return (ans==2*maxiN?-1:ans);
}

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