제출 #1126792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126792		Ludissey	경주 (Race) (IOI11_race)	C++20	0 / 100	1 ms	320 KiB

race

#include "race.h"

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
using namespace std;
 
vector<vector<pair<int,int>>> neigh;
vector<vector<int>> child;
vector<int> parent;
vector<int> ta;
vector<int> childC;
vector<int> hide;
vector<int> cindx;
vector<int> dep;
unordered_set<int> tch;
int n;
int K;
int ct=0;
int _n=0;
 
int build_tree(int x, int p){
    childC[x]=1;
    for (int t=0; t<sz(neigh[x]); t++)
    {
        int u=neigh[x][t].first;
        if(u==p||cindx[u]>=0) continue;
        childC[x]+=build_tree(u,x);
    }
    return childC[x];
}
 
int centroid(int x, int p){
    for (int t=0; t<sz(neigh[x]); t++)
    {
        int u=neigh[x][t].first;
        if(u==p||cindx[u]>=0) continue;
        if(childC[u]*2>=_n) return centroid(u,x);
    }
    return x;
}
 
void calk(int x, int d, int d2, int mn, int p){
    if(d>K) return;
    dep[d]=min(d2,dep[d]);
    tch.insert(d);
    for (auto u : neigh[x])
    {
      if(u.first==p||mn>=cindx[u.first]) continue;
      calk(u.first, d+u.first, d2+1, mn, x);
    }
    return;
}

int dfs(int x, int p){
  vector<unordered_map<int,int>> al(sz(neigh[x]));
  map<int,pair<int,int>> cmp;
  int mx=0;
  for (int t=0; t<sz(neigh[x]); t++)
  {
    if(cindx[neigh[x][t].first]<=cindx[x]) continue;
    tch.clear();
    calk(neigh[x][t].first,neigh[x][t].second,1,cindx[x],x);
    for (auto u: tch)
    {
      al[t][u]=dep[u];
      if(cmp[u].first==0) cmp[u].first=t+1;
      else if(cmp[u].second==0) cmp[u].second=t+1;
      else{
        if(al[cmp[u].first-1][u]>dep[u]) cmp[u].first=t+1;
        else if(al[cmp[u].second-1][u]>dep[u]) cmp[u].second=t+1;
      }
      dep[u]=1e9;
    }
  }
  int mn=1e9;
  for (int t=0; t<sz(neigh[x]); t++){
    for (auto u : al[t])
    {
      int d=u.first; int v=u.second;
      int nd=K-d;
      int v2=1e9;
      if(nd==0){
        mn=min(v,mn);
        continue;
      }
      if(cmp[nd].first==0) continue;
      else{
        if(cmp[nd].first==t+1){
          if(cmp[nd].second==0) continue;
          else v2=al[cmp[nd].second-1][nd];
        }else v2=al[cmp[nd].first-1][nd];
      }
      mn=min(v+v2,mn);
    }
  }
  for (auto u : neigh[x])
  {
    if(u.first==p) continue;
    mn=min(mn,dfs(u.first, x));
  }
  return mn;
}

void decompo(int x, int compoINDEX){
  build_tree(x,-1);
  _n=childC[x];
  int c=centroid(x,-1);
  cindx[c]=compoINDEX;
  for (auto u : neigh[c])
  {
    if(cindx[u.first]>=0) continue;
    decompo(u.first,compoINDEX+1);
  }
}
 
int best_path(int N, int _K, int H[][2], int L[])
{
  K=_K;
  n=N;
  neigh.resize(n);
  cindx.resize(n);
  dep.resize(K+1,1e9);
  childC.resize(n,0);
  for (int i = 0; i < n-1; i++)
  {
      int a=H[i][0],b=H[i][1]; 
      neigh[a].push_back({b,L[i]});
      neigh[b].push_back({a,L[i]});
  }
  cindx.clear(); cindx.resize(n,-1);
  childC.resize(n);
  decompo(0,0);
  for (int i = 0; i < n; i++)
  {
      if(cindx[i]<0) cindx[i]=1e5;
  }
  int res=dfs(0,-1);
  if(res>n) return -1;
  return res;
}

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