Submission #920205

#	Time	Username	Problem	Language	Result	Execution time	Memory
920205		Arp	Race (IOI11_race)	C++17	100 / 100	341 ms	43540 KiB

race

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
const int N = 2e5 + 5;
const int K = 1e6;
vector<pair<int,int>> adj[N];
int sz[N];
int depth[N];
int md[K + 1];
i64 dist[N];
bool vis[N];
 
int k;
int ans = N + 1;
 
void find_size(int u,int p){
  sz[u] = 1;
  for(auto [v,w] : adj[u]){
    if(vis[v] || v == p) continue;
    find_size(v,u);
    sz[u] += sz[v];
  }
}
 
// Find Centeroid of the subtree of u
int findC(int u,int p,int S){
  for(auto [v,w] : adj[u]){
    if(vis[v] || v == p) continue;
    if(sz[v] > S / 2){
      return findC(v,u,S);
    }  
  }
  return u;
}
 
vector<int> ad;
vector<int> rem;
void dfs(int u,int p){
  vector<vector<int>> all;
  for(auto [v,w] : adj[u]){
    if(v == p || vis[v]) continue;
    depth[v] = depth[u] + 1;
    dist[v] = dist[u] + w;
    ad.push_back(v);
    dfs(v,u);
    if(p == -1){
      all.push_back(ad);
      ad.clear();
    }
  }
  if(p != -1) return;
  for(auto &vec : all){
    for(auto &v: vec){
      if(dist[v] <= k){
        ans = min(ans,depth[v] + md[k - dist[v]]);
      } 
    }
    for(auto &v : vec){
      if(k < dist[v]) continue;
      md[dist[v]] = min(md[dist[v]],depth[v]);
      rem.push_back(dist[v]);
    }
  }
}
 
// Initialize the subtree of u based on the array vis
void init(int u,int p){
  find_size(u,p);
  int C = findC(u,p,sz[u]);
  vis[C] = true;
  ad.clear();
  depth[C] = 0;
  dist[C] = 0;
  md[0] = 0;
  for(int &w : rem){
    md[w] = N + 1;
  }
  rem.clear();
  dfs(C,-1);  
  for(auto [v,w] : adj[C]){
    if(vis[v]) continue;
    init(v,C);
  } 
}

int best_path(int n,int K,int H[][2],int L[]){
  for(int i = 0;i<N;i++){
    vis[i] = false;
  }
  for(int i = 0;i <= K;i++){
    md[i] = N + 1;
  }
  for(int i = 0;i<n - 1;i++){
    adj[H[i][0]].emplace_back(H[i][1],L[i]);
    adj[H[i][1]].emplace_back(H[i][0],L[i]);
  }
  k = K;
  init(0,-1);
  return (ans > n ? -1 : ans);
}

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