Submission #1097323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097323		greenbinjack	Race (IOI11_race)	C++17	100 / 100	683 ms	39440 KiB

race

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

#define all(v) v.begin(), v.end()

using LL = long long; 

const int N = 2E5 + 69;

vector < pair <int, int> > G[N];
int k, mx_depth, sz[N], pa[N], processed[N], l[N];
map <int, int> mp;
int ans = INT_MAX;

int dfs (int u, int p) {
  sz[u] = 1;
  for(auto [v, idx] : G[u]) if (v != p and !processed[v]) {
    sz[u] += dfs(v, u);
  }
  return sz[u];
}
int centroid (int u, int p, int n) {
  for(auto [v, idx] : G[u]) if(v != p and !processed[v]) {
    if (sz[v] > n / 2) return centroid (v, u, n);
  }
  return u;
}
void get_cnt (int u, int p, bool filling, int len, int depth = 1) {
  // cerr << ((filling) ? "FILLING " : "QUERY ") << u << ' ' << p << ' ' << len << ' ' << depth << '\n';
  if (len > k) return;
  // mx_depth = max (mx_depth, depth);
  if (filling) {
    if (mp.count (len)) mp[len] = min (mp[len], depth);
    else mp[len] = depth;
    // cerr << "UPDATED: " << len << ' ' << mp[len] << endl;
  }
  else {
    // cerr << "QUERYING " << k - len << '\n';
    if (mp.count (k - len)) ans = min (ans, mp[k - len] + depth);
  }
  for (auto [next, idx] : G[u]) if (next != p and !processed[next]) {
    get_cnt (next, u, filling, len + l[idx], depth + 1);
  }
}
void build (int u = 0, int p = -1) {
  int n = dfs (u, p);
  int c = centroid (u, p, n);
  processed[c] = 1;

  // cerr << c << endl;
  // mx_depth = 0;
  for (auto [next, idx] : G[c]) if (next != p and !processed[next]) {
    get_cnt (next, c, false, l[idx]);
    // for (auto [l, r] : mp) cerr << l << ' ' << r << endl;
    get_cnt (next, c, true, l[idx]);
  }
  if (mp.count (k)) ans = min (ans, mp[k]);

  mp.clear ();
  for (auto [next, idx] : G[c]) {
    if (!processed[next]) build (next, c);
  }
}

int best_path (int N, int K, int H[][2], int L[]) {
  k = K;
  for (int i = 0; i < N; i++) l[i] = L[i];
  for (int i = 0; i < N - 1; i++) {
    G[H[i][0]].push_back ({H[i][1], i});
    G[H[i][1]].push_back ({H[i][0], i});
  }
  build ();
  if (ans == INT_MAX) ans = -1;
  return ans;
}

// int main() {
//   cin.tie(nullptr) -> ios_base::sync_with_stdio(false);

//   int n, kk;
//   cin >> n >> kk;
//   int H[n][2], L[n];
//   for (int i = 0; i < n - 1; i++) cin >> H[i][0] >> H[i][1];
//   for (int i = 0; i < n; i++) cin >> L[i];

//   cout << best_path (n, kk, H, L) << '\n';
  
//   return 0; 
// }

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