Submission #1317711

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

race

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

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

int n;
vector < pair < int , int > > G[N];
vector < pair < int , pair < int , int > > > anc[N] , arc[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];
bool is_rmv[N];
int up[19][N];
int dep[N];

void DFS(int v , int p)
{
   if(v > 0) dep[v] = dep[p] + 1;
   up[0][v] = p;
   for(int i = 1;i < 19;i++) up[i][v] = up[i - 1][up[i - 1][v]];
   for(pair < int , int > nxt : G[v]){
      int u = nxt.first;
      if(u != p) DFS(u , v);
   }
}

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;
}
void dfs(int v , int p , int centro , int nd , int wd)
{
   anc[v].push_back({centro , {wd , nd}});
   arc[centro].push_back({v , {wd , nd}});
   for(pair < int , int > nxt : G[v])
   {
      int u = nxt.first;
      if(u != p && !is_rmv[u]) dfs(u , v , centro , nd + 1 , wd + nxt.second);
   }
}
void build(int v)
{
   int comp_sz = gsz(v , -1);
   int centro = find_centro(v , -1 , comp_sz);
   is_rmv[centro] = 1;
   dfs(centro , -1 , centro , 0 , 0);
   for(pair < int , int > nxt : G[centro]){
      int u = nxt.first;
      if(!is_rmv[u]) build(u);
   }
}
int LCA(int u , int v)
{
   if(dep[u] < dep[v]) swap(u , v);
   int dif = dep[u] - dep[v];
   for(int i = 18;i >= 0;i--)
   {
      if((1 << i) & dif) u = up[i][u];
   }
   if(u == v) return u;
   for(int i = 18;i >= 0;i--)
   {
      if(up[i][u] != up[i][v])
      {
         u = up[i][u];
         v = up[i][v];
      }
   }
   return up[0][u];
}
int dis(int u , int v)
{
   int lca = LCA(u , v);
   return (dep[v] - dep[lca]) + (dep[u] - dep[lca]);
}
int get(int v , int k)
{
   int ans = INF;
   for(pair < int , pair < int , int > > nxt1 : anc[v])
   {
      int centro = nxt1.first;
      int wg = nxt1.second.first;
      int ng = nxt1.second.second;
      int need = k - wg;
      for(pair < int , pair < int , int > > nxt2 : arc[centro])
      {
         int node = nxt2.first;
         int wgg = nxt2.second.first;
         int ngg = nxt2.second.second;
         if(wgg != need) continue;
         if(dis(v , centro) > dis(v , node)) continue;
         ans = min(ans , ng + ngg);
      }
   }
   return ans;
}

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

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