Submission #1126809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126809		Ludissey	Race (IOI11_race)	C++20	43 / 100	3090 ms	29352 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 solu=1e9;
 
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 p){
  if(d>K) return;
  dep[d]=min(d2,dep[d]);
  tch.insert(d);
  for (auto u : neigh[x])
  {
    if(u.first==p||cindx[u.first]>0) continue;
    calk(u.first, d+u.second, d2+1, x);
  }
  return;
}
vector<pair<pair<int,int>,pair<int,int>>> cmp;
vector<vector<pair<int,int>>> al;

void dfs(int x){
  for (int t=0; t<sz(neigh[x]); t++)
  {
    al[t].clear();
    if(cindx[neigh[x][t].first]>0) continue;
    tch.clear();
    calk(neigh[x][t].first,neigh[x][t].second,1,x);
    for (auto u: tch)
    {
      al[t].push_back({u,dep[u]});
      if(cmp[u].first.first==0) cmp[u].first={t+1,al[t].back().second};
      else if(cmp[u].second.first==0) cmp[u].second={t+1,al[t].back().second};
      else{
        if(cmp[u].first.second>dep[u]) cmp[u].first={t+1,al[t].back().second};
        else if(cmp[u].second.second>dep[u]) cmp[u].second={t+1,al[t].back().second};
      }
      dep[u]=1e9;
    }
  }
  int mn=1e9;
  for (int t=0; t<sz(neigh[x]); t++){
    for (int j=0; j<sz(al[t]); j++)
    {
      int d=al[t][j].first; int v=al[t][j].second;
      int nd=K-d;
      int v2=1e9;
      if(nd==0){
        mn=min(v,mn);
        continue;
      }
      if(cmp[nd].first.first==0) continue;
      else{
        if(cmp[nd].first.first==t+1){
          if(cmp[nd].second.first==0) continue;
          else v2=cmp[nd].second.second;
        }else v2=cmp[nd].first.second;
      }
      mn=min(v+v2,mn);
    }
  }
  for (int t=0; t<sz(neigh[x]); t++){
    for (int j=0; j<sz(al[t]); j++)
    {
      int d=al[t][j].first;
      cmp[d]={{0,0},{0,0}};
    }
  }
  solu=min(mn,solu);
}

void decompo(int x, int compoINDEX){
  build_tree(x,-1);
  _n=childC[x];
  int c=centroid(x,-1);
  cindx[c]=compoINDEX;
  dfs(c);
  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);
  al.resize(n);
  dep.resize(K+1,1e9);
  cmp.resize(K+1,{{0,0},{0,0}});
  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);
  solu=1e9;
  decompo(0,0);
  for (int i = 0; i < n; i++)
  {
      if(cindx[i]<0) cindx[i]=1e5;
  }
  if(solu>n) return -1;
  return solu;
}

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