Submission #1004368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004368		Gray	Race (IOI11_race)	C++17	9 / 100	235 ms	12720 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;
void gensz(ll u, ll p){
  sz[u]=1;
  for (auto i:A[u]){
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    if (v==p) continue;
    gensz(v, u);
    sz[u]+=sz[v];
  }
}
void findcentroid(ll u, ll p, ll up, ll &centr, ll wsz){
  bool pos=(up<=wsz/2);
  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) pos=0;
    findcentroid(v, u, up+1, centr, wsz);
  }
  if (pos) centr=u;
}
void cedfs(ll u, ll &mn, ll wsz, map<ll, ll> &add){
  ll centr = -1;
  findcentroid(u,u, 0, centr, wsz);
  assert(centr!=-1);
  map<ll, ll> lens;
  for (auto i:A[u]){
    if (black[i]) continue;
    black[i]=1;
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    lens.clear();
    cedfs(v, mn, sz[v], lens);
    // cout << v << ": ";
    for (auto [length, tim]:lens){
      // cout << length << "-" << tim << ' ';
      if (add.count(k-length-e[i].ff)){
        mn=min(mn, add[k-length-e[i].ff]+tim+1);
      }
      if (length+e[i].ff==k){
        mn=min(mn, tim+1);
      }
    }
    // cout << ln;
    for (auto [length, tim]:lens){
      if (add.count(length+e[i].ff)){
        add[length+e[i].ff]=min(add[length+e[i].ff], tim+1);
      }else{
        add[length+e[i].ff]=tim+1;
      }
    }
    add[e[i].ff]=1;
  }
}


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;
  gensz(0, 0);
  map<ll, ll> cnt;
  cedfs(0, mn, sz[0], cnt);
  return (mn==2e18?-1:mn);
}

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