Submission #784681

#	Time	Username	Problem	Language	Result	Execution time	Memory
784681		bane	Race (IOI11_race)	C++17	43 / 100	3067 ms	36388 KiB

race

#include<bits/stdc++.h>
#include "race.h"
#define ll long long
using namespace std;

struct Undirected_Graph{
  
  int N, K, ans = (int)1e9;
  vector<vector<pair<int,int>>>adj;
  vector<int>Used;
  vector<int>Sz;
  unordered_map<ll,ll>dp;
  vector<int>vec;

  Undirected_Graph(int _N, int _K, int H[0][2], int L[]):N(_N),K(_K){
    adj.resize(N);
    Used.resize(N);
    Sz.resize(N);
    for (int i = 0; i < N - 1; i++){
      adj[H[i][1]].push_back({H[i][0], L[i]});
      adj[H[i][0]].push_back({H[i][1], L[i]});
    }
  }

  int Make(int U, int P){
    Sz[U] = 1;
    for (auto [f,w] : adj[U]){
      if (f == P || Used[f])continue;
      Sz[U] += Make(f,U);
    }
    return Sz[U];
  }

  int Who(int U, int P, int Des){
    for (auto [f,w] : adj[U]){
      if (f == P || Used[f])continue;
      if (Sz[f] * 2 > Des)return Who(f,U,Des);
    }

    return U;
  }

  void put(int u, int p, int depth, int orz){
    if (depth > K)return;
    if (!dp.count(depth))dp[depth] = (int)1e9;
    dp[depth] = min(dp[depth], (ll)orz);
    for (auto [f,w] : adj[u]){
      if (f == p || Used[f])continue;
      put(f,u,depth+w,orz+1);
    }
  }

  void Dfs(int u, int p, int depth, int orz){
    if (depth > K)return;
    if (!dp.count(K - depth))dp[K - depth] = (int)1e9;
    ans = min((ll)ans, dp[K - depth] + orz);
    for (auto [f,w] : adj[u]){
      if (f == p || Used[f])continue;
      Dfs(f,u,depth+w,orz+1);
    }
  }

  void Centroid_Decomposition(int U, int P){
    int Centroid = Who(U,P, Make(U,P));
    dp.clear();
    dp[0] = 0;
    for (auto [f,w] : adj[Centroid]){
      if (Used[f] || f == P)continue;
      Dfs(f,Centroid,w,1);
      put(f,Centroid,w,1);
    }

    Used[Centroid] = 1;

    for (auto [f,w] : adj[Centroid]){
      if (Used[f] || f == P)continue;
      Centroid_Decomposition(f,Centroid);
    }
  }
};

int best_path(int N, int K, int H[][2], int L[])
{

  Undirected_Graph G(N,K,H,L);
  G.Centroid_Decomposition(0,-1);
  return (G.ans == (int)1e9 ? -1 : G.ans);
}

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