Submission #569001

#	Time	Username	Problem	Language	Result	Execution time	Memory
569001		d4xn	Race (IOI11_race)	C++17	9 / 100	740 ms	262144 KiB

race

#include "race.h"

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

#define ll long long
#define vi vector<ll>
#define ii pair<ll, ll>
#define vii vector<ii>
#define pb push_back
#define mp make_pair

const ll mxN = 2e5+5, inf = 1e18;

ll n, k;
vii adj[mxN];
ll dis[mxN]; // dis de 0 a x
ll p[mxN];
map<ll, ll> dp[mxN]; // min len de path de peso x

void dfs(ll u = 0, ll par = -1, ll d = 0) {
  p[u] = par;
  dis[u] = d;

  for (auto &[v, w] : adj[u]) {
    if (v == par) continue;
    dfs(v, u, d+w);

    dp[u][w] = 1;
    for (auto &[x, y] : dp[v]) {
      if (w+x > k) break;

      auto it = dp[u].find(x+w);
      if (it == dp[u].end()) dp[u][x+w] = y+1;
      else it->second = min(it->second, y+1);
    }
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  n = N;
  k = K;
  for (ll i = 0; i < n-1; i++) {
    ll x = H[i][0];
    ll y = H[i][1];
    adj[x].pb(mp(y, L[i]));
    adj[y].pb(mp(x, L[i]));
  }

  dfs();

  ll mn = inf;
  for (ll i = 0; i < n; i++) {
    auto it = dp[i].find(k);
    if (it != dp[i].end()) {
      mn = min(mn, it->second);
    }

    ll cnt = 1;
    ll x = p[i];
    ll son = i;
    while (x != -1) {
      for (auto &[v, w] : adj[x]) {
        if (v == son || v == p[x]) continue;
        
        ll d = dis[i] - dis[x] + w;
        if (d >= k) break;

        auto it2 = dp[v].find(k-d);
        if (it2 != dp[v].end()) {
          mn = min(mn, cnt+1 + it2->second);
        }
      }

      son = x;
      x = p[x];
      cnt++;
    }
  }

  return mn == inf ? -1 : mn;
}

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