Submission #1004520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004520		Gray	Race (IOI11_race)	C++17	21 / 100	1848 ms	262144 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"
vector<pair<ll, pair<ll, ll>>> e;
vector<vector<ll>> A;
vector<bool> black;
vector<ll> sz;
ll n, k;
ll getsz(ll u, ll p){
  sz[u]=1;
  for (auto i:A[u]){
    if (black[i]) continue;
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    if (v==p) continue;
    sz[u]+=getsz(v, u);
  }
  return sz[u];
}
void findcentroid(ll u, ll p, ll up, ll &centr, ll wsz){
  for (auto i:A[u]){
    if (black[i]) continue;
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    if (v==p) continue;
    if (sz[v]>wsz/2) {findcentroid(v, u, up+1, centr, wsz); return;}
  }
  centr=u;
  return;
}
void dfs(ll u, ll p, set<pair<ll, ll>> &usg, ll level, ll dep){
  auto it = usg.lower_bound({level, -1});
  if (usg.empty() or it==usg.end() or ((*it).ff==level and (*it).ss>dep) or (*it).ff!=level) {
    if (!usg.empty() and it!=usg.end() and (*it).ff==level){
      usg.erase(it);
    }
    usg.insert({level, dep});
  }
  for (auto i:A[u]){
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    if (v==p or black[i]) continue;
    dfs(v, u, usg, level+e[i].ff, dep+1);
  }
}
void cedfs(ll u, ll &mn, ll wsz){
  ll centr = -1;
  findcentroid(u,u, 0, centr, wsz);
  assert(centr!=-1);
  set<pair<ll, ll>> levs, full;
  for (auto i:A[u]){
    if (black[i]) continue;
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    levs.clear();
    dfs(v, u, levs, e[i].ff, 1);
    for (auto [length, tim]:levs){
      auto it = full.lower_bound({k-length, -1});
      if (!full.empty() and it!=full.end() and (*it).ff==k-length){
        mn=min(mn, tim+(*it).ss);
      }
      if (length==k) {
        mn=min(mn, tim);
      }
    }
    // cout << ln;
    for (auto [length, tim]:levs){
      full.insert({length, tim});
    }
  }
  for (auto i:A[u]){
    if (black[i]) continue;
    black[i]=1;
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    cedfs(v, mn, getsz(v, v));
  }
}


int best_path(int N, int K, int H[][2], int L[])
{
  n = N; k=K;
  e.resize(N-1);
  A.resize(N);
  for (ll i=0; i<n-1; i++){
    A[H[i][0]].push_back(i);
    A[H[i][1]].push_back(i);
    e[i] = {L[i], {H[i][0], H[i][1]}};
  }
  black.resize(N);
  sz.resize(N);
  ll mn = 2e18;
  cedfs(0, mn, getsz(0, 0));
  return (mn==2e18?-1:mn);
}

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