Submission #953421

#	Time	Username	Problem	Language	Result	Execution time	Memory
953421		Maaxle	Race (IOI11_race)	C++17	0 / 100	12 ms	21340 KiB

race

#include "race.h"
#include <bits/stdc++.h>
  
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 60)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue
#define ptr(A) shared_ptr<A>
  
using namespace std;
  
struct Path {
  ll i, w;
};
  
ll n, k;
ll ans = INF64;
vector<vector<Path>> adj;
vector<bool> wasCentroid;
vector<ll> subtree;
  
void find_subtree(ll& i, ll& from) {
  subtree[i] = 1;
  for (Path& k : adj[i]) {
    if (k.i != from && !wasCentroid[k.i] && k.i != i) {
      find_subtree(k.i, i);
      subtree[i] += subtree[k.i];
    }
  }
}
  
ll find_centroid(ll& i, ll& from, ll& N) {
  for (Path& k : adj[i]) {
    if (k.i != from && !wasCentroid[k.i] && subtree[k.i] > n/2 && k.i != i) 
      return find_centroid(k.i, i, N);
  }
  return i;
}
  
vector<ll> freq ((1 << 20), INF64);
void find_ans(ll& i, ll& from, vector<Path>& cur, ll cnt, ll w) {
  if (w > k)
    return;
  if (w == k) {
    ans = min(ans, cnt);
    return;
  }
  
  if (freq[k-w] != INF64) {
    ans = min(ans, freq[k-w]+cnt);
  }
  
  cur.push_back({cnt, w});
  for (Path& k : adj[i]) {
    if (!wasCentroid[k.i] && k.i != from && k.i != i) 
      find_ans(k.i, i, cur, cnt+1, w+k.w);
  }
}
  
void clean (ll& i, ll& from, ll w) {
  freq[w] = INF64;
  for (Path& k : adj[i]) {
    if (k.i != from && !wasCentroid[k.i] && k.i != i)
      clean(k.i, i, w+k.w);
  }
}
  
void process(ll& i) {
  for (Path& k : adj[i]) {
    if (!wasCentroid[k.i] && k.i != i) {
      vector<Path> cur;
      find_ans(k.i, i, cur, 1, k.w);
      for (Path& it : cur) {
        freq[it.w] = min(freq[it.w], it.i);
      }
    }
  }
  clean(i, i, 0);
}
  
void answer(ll i) {
  find_subtree(i, i);
  ll N = subtree[i];
  i = find_centroid(i, i, N);
  process(i);
  wasCentroid[i] = 1;
  for (Path& k : adj[i]) {
    if (!wasCentroid[k.i] && k.i != i)
      answer(k.i);
  }
}
  
int best_path(int N, int K, int H[][2], int L[]) {
  n = N; k = K;
  adj.resize(n);
  wasCentroid.resize(n);
  subtree.resize(n);
  
  range(i, 0, n) {
    adj[H[i][0]].push_back({H[i][1], L[i]});
    adj[H[i][1]].push_back({H[i][0], L[i]});
  }
  
  answer(0);
  
  return (ans == INF64 ? -1 : ans);
}

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