Submission #1004266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004266		Gray	Race (IOI11_race)	C++17	100 / 100	440 ms	94092 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;
ll n, k;

ll sortsz(ll u, ll p){
  ll sz=0;
  ll mx=0;
  for (auto &i:A[u]){
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    if (v==p) continue;
    ll ret = sortsz(v, u);
    sz+=ret;
    if (ret>mx){
      swap(A[u][0], i);
      mx=ret;
    }
  }
  return sz;
}
void dfs(ll u, ll p, map<ll, ll> &len, ll &mn, ll addx, ll addy){
  bool first=1;
  map<ll, ll> nw;
  for (auto i:A[u]){
    ll v = e[i].ss.ff^e[i].ss.ss^u;
    if (v==p) continue;
    if (first){
      dfs(v, u, len, mn, addx+e[i].ff, addy+1);
      if (len.count(k+addx)){
        mn = min(mn, len[k+addx]-addy);
      }
      first=0;
    }else{
      dfs(v, u, nw, mn, e[i].ff, 1);
      for (auto [length, tim]:nw){
        if (length==k){
          mn=min(mn, tim);
        }
        // cout << "check: " << length << "-" << tim << " to " << addx << ln;
        if (len.count(addx+(k-length)) and k-length>=0){
          mn=min(mn, len[addx+(k-length)]-addy+tim);
        }
      }
      for (auto [length, tim]:nw){
        if (len.count(addx+length)){
          len[length+addx] = min(tim+addy, len[length+addx]);
        }else{
          len[length+addx] = tim+addy;
        }
      }
      nw.clear();
    }
  }
  if (u!=p){
    if (len.count(addx)){
      len[addx]=min(len[addx], addy);
    }else{
      len[addx]=addy;
    }
  }
  // cout << u << ": ";
  // for (auto ch:len){
  //   cout << ch.ff << "-" << ch.ss << " "; 
  // }
  // cout << ln;
}
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]}};
  }
  sortsz(0, 0);
  ll mn = 2e18;
  map<ll, ll> length;
  dfs(0, 0, length, mn, 0, 0);
  // for (auto ch:length){
  //   cout << ch.ff << "-" << ch.ss << ln;
  // }
  return (mn==2e18?-1:mn);
}

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