Submission #1317992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317992		ElayV13	Race (IOI11_race)	C++20	100 / 100	1403 ms	55820 KiB

race

#include "race.h"
#include "bits/stdc++.h"
using namespace std;

const int N = 200001;
const int INF = 1e9;

int n , k , ans = INF;
vector < pair < int , int > > G[N];
void add_edge(int u,int v,int w){
   G[u].push_back({v , w});
   G[v].push_back({u , w});
}
int sub[N] , par[N];
bool is_rmv[N];

int gsz(int v , int p){
   sub[v] = 1;
   for(pair < int , int > nxt : G[v]){
      int u = nxt.first;
      if(u == p or is_rmv[u]) continue;
      sub[v] += gsz(u , v);
   }
   return sub[v];
}
int find_centro(int v , int p , int need){
   for(pair < int , int > nxt : G[v])
   {
      int u = nxt.first;
      if(u == p or is_rmv[u] or sub[u] <= need / 2) continue;
      return find_centro(u , v , need);
   }
   return v;
}
map < int , int > mn;
map < int , int > can;
vector < pair < int , int > > all;
void dfs(int v , int p , int nd , int wd , int centro)
{
   all.push_back({nd , wd});
   int need = k - wd;
   if(can[need])
   {
      ans = min(ans , nd + mn[need]);
   }
   for(pair < int , int > nxt : G[v])
   {
      int u = nxt.first;
      if(u != p && !is_rmv[u]) dfs(u , v , nd + 1 , wd + nxt.second , centro);
   }
}
void build(int v)
{
   int comp_sz = gsz(v , -1);
   int centro = find_centro(v , -1 , comp_sz);
   can.clear();
   mn.clear();
   can[0] = 1;
   mn[0] = 0;
   for(pair < int , int > nxt : G[centro])
   {
      all.clear();
      int u = nxt.first;
      if(!is_rmv[u])
      {
         dfs(u , centro , 1 , nxt.second , centro);
         for(pair < int , int > mnp : all)
         {
            int dsc = mnp.first;
            int wg = mnp.second;
            if(!can[wg])
            {
               can[wg] = 1;
               mn[wg] = dsc;
            }
            else mn[wg] = min(mn[wg] , dsc);
         }
      }
   }
   is_rmv[centro] = 1;
   for(pair < int , int > nxt : G[centro]){
      int u = nxt.first;
      if(!is_rmv[u]) build(u);
   }
}

int best_path(int N , int K , int H[][2] , int L[])
{
   n = N; k = K;
   for(int i = 0;i < N - 1;i++) add_edge(H[i][0] , H[i][1] , L[i]);
   build(0);
   if(ans == INF) ans = -1;
   return ans;
}

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