Submission #1162021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162021		spycoderyt	경주 (Race) (IOI11_race)	C++20	0 / 100	3 ms	7488 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N = 3e5+5;
int K;
int rem[N],sz[N];
int ans = 1e9;
vector<pair<int,int> > A[N];
vector<int> dislist;
map<ll,int>mp;
int sub_sz(int u,int par = -1) {
  sz[u]=1;
  for(auto [nxt,w] : A[u]) if(nxt!=par&&!rem[nxt])sz[u]+=sub_sz(nxt,u);
  return sz[u];
}
int find_cen(int u,int sub_sz,int par = -1) {
  for(auto [nxt,w] : A[u])if(nxt!=par&&!rem[nxt]&&2*sz[nxt] > sub_sz)return find_cen(nxt,sub_sz,u);
  return u;
}
void get_cnt(int u,int par = -1,int fill = 0,int dep = 0,ll dis = 0){
  if(dis>K)return;
  if(fill){
    if(mp[dis])mp[dis] = min(mp[dis], dep);
    else mp[dis] = dep;
  }
  else {
    if(mp[K-dis])ans = min(ans,mp[K-dis]+dep);
    if(dis==K)ans=min(ans,dep);
  }
  for(auto [nxt,w] : A[u])if(nxt!=par && !rem[nxt]) get_cnt(nxt,u,fill,dep+1,dis+w);
}
void build(int u=1) {
  int cen = find_cen(u,sub_sz(u));
  rem[cen]=1;
  for(auto [nxt,w] : A[u]) if(!rem[nxt])get_cnt(nxt,u,0,1,w),get_cnt(nxt,u,1,1,w);
  mp.clear();
  for(auto [nxt,w] : A[u]) if(!rem[nxt])build(nxt);
}
int best_path(int n, int k, int h[][2], int w[])
{
  K=k;
  for(int i = 0;i<n-1;i++) {
    int a = h[i][0], b = h[i][1];
    A[a].push_back({b,w[i]});
    A[b].push_back({a,w[i]});
  }
  build();
  if(ans>=1e9)return -1;
  else return ans;
}

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