제출 #1322824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1322824		hgia	경주 (Race) (IOI11_race)	C++17	0 / 100	3 ms	4920 KiB

race

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,k,ans=1e9;
int sz[N],h[N],dist[N];
bool del[N];
int best[1000005];
vector<pair<int,int>>d[N];
vector<int>used;
vector<pair<int,int>>neww;
void dfs(int u,int p)
{
  sz[u]=1;
  for(auto i:d[u])
  {
    int v=i.second;
    if(v==p||del[v])continue;
    dfs(v,u);
    sz[u]+=sz[v];
  }
}
int findroot(int u,int p,int n)
{
  for(auto i:d[u])
  {
    int v=i.second;
    if(v==p||del[v])continue;
    if(sz[v]>n/2)return findroot(v,u,n);
  }
  return u;
}
void caldist(int u,int p,int w)
{
  dist[u]=dist[p]+w;
  h[u]=h[p]+1;
  if(dist[u]>k)return;
  neww.push_back({dist[u],h[u]});
  used.push_back(dist[u]);
  ans=min(ans,h[u]+best[k-dist[u]]);
  for(auto i:d[u])
  {
    int v=i.second;
    w=i.first;
    if(v==p||del[v])continue;
    caldist(v,u,w);
  }
}
void updateans(int u)
{
  used.clear();
  for(auto i:d[u])
  {
    int v=i.second;
    int w=i.first;
    if(del[v])continue;
    neww.clear();
    caldist(v,u,w);
    for(auto tmp:neww)best[tmp.first]=min(best[tmp.first],tmp.second);
  }
  for(auto tmp:used)best[tmp]=1e9;
}
void solve(int u)
{
  dfs(u,0);
  int root=findroot(u,0,sz[u]);
  best[0]=0;
  h[root]=0;
  dist[root]=0;
  updateans(root);
  del[root]=true;
  for(auto i:d[root])
  {
    int v=i.second;
    if(del[v])continue;
    solve(v);
  }
}
int best_path(int n_,int k_,int edge[][2],int w[])
{
  for(int i=0;i<n_-1;i++)
  {
    int u=edge[i][0];
    int v=edge[i][1];
    int tmp=w[i];
    u++;
    v++;
    d[u].push_back({tmp,v});
    d[v].push_back({tmp,u});
  }
  n = n_; k = k_;
  ans = 1e9;
  for(int i=1;i<=n;i++){ d[i].clear(); del[i]=false; }
  for(int i=0;i<=k;i++) best[i]=1e9;
  solve(1);
  if(ans==1e9)ans=-1;
  return ans;
}

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