Submission #569033

#	Time	Username	Problem	Language	Result	Execution time	Memory
569033		d4xn	Race (IOI11_race)	C++17	21 / 100	3027 ms	47596 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, inf = 2e9;
 
int n, k, d2;
vii adj[mxN];
int dis[mxN]; // dis de 1 a x
int p[mxN];
set<int> dp[mxN]; // min len de path de peso x
 
void dfs(int u = 0, int par = -1) {
  p[u] = par;
  
  for (auto &[v, w] : adj[u]) {
    if (v == par) continue;

    dis[v] = dis[u]+w;
    dfs(v, u);
 
    if (w <= k && w) dp[u].insert(w);
    for (auto x : dp[v]) {
      //if (x+w > k || !x) continue;
      if (x+w > k) break;
      if (!x) continue;
      dp[u].insert(x+w);
    }
  }
}
 
void findPath(int u, int par, int d) {
  if (d == 0) return;
  for (auto &[v, w] : adj[u]) {
    if (v == par || (d-w != 0 && dp[v].find(d-w) == dp[v].end())) continue;
    d2++;
    findPath(v, u, d-w);
  }
}

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]));
  }

  dis[0] = 0;
  dfs();
 
  int mn = inf;
  for (int i = 0; i < n; i++) {
    auto it = dp[i].find(k);
    if (it != dp[i].end()) {
      d2 = 0;
      findPath(i, p[i], k);
      mn = min(mn, d2);
    }
 
    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;

        if (k == d) {
          mn = min(mn, cnt+1);
          continue;
        }

        auto it2 = dp[v].find(k-d);
        if (it2 != dp[v].end()) {
          d2 = 0;
          findPath(v, p[v], k-d);
          mn = min(mn, cnt+1 + d2);
        }
      }
 
      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