Submission #569003

#	Time	Username	Problem	Language	Result	Execution time	Memory
569003		d4xn	Race (IOI11_race)	C++17	21 / 100	750 ms	262144 KiB

race

#include "race.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define pb push_back
#define mp make_pair
 
const int mxN = 2e5+5, inf = 2e9;
 
int n, k;
vii adj[mxN];
int dis[mxN]; // dis de 1 a x
int p[mxN];
map<int, int> dp[mxN]; // min len de path de peso x
 
void dfs(int u = 0, int par = -1, int d = 0) {
  p[u] = par;
  dis[u] = d;
 
  dp[u][0] = 0;
  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 (x+w > 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 (int i = 0; i < n-1; i++) {
    int x = H[i][0];
    int y = H[i][1];
    adj[x].pb(mp(y, L[i]));
    adj[y].pb(mp(x, L[i]));
  }
 
  dfs();
 
  int mn = inf;
  for (int i = 0; i < n; i++) {
    auto it = dp[i].find(k);
    if (it != dp[i].end()) {
      mn = min(mn, it->second);
    }
 
    int cnt = 1;
    int x = p[i];
    int son = i;
    while (x != -1) {
      for (auto &[v, w] : adj[x]) {
        if (v == son || v == p[x]) continue;
        
        int d = dis[i] - dis[x] + w;
        if (d > k) continue;

        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: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57