Submission #936082

#	Time	Username	Problem	Language	Result	Execution time	Memory
936082		Yell0	Race (IOI11_race)	C++17	100 / 100	1266 ms	60628 KiB

race

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int MN=2e5+2;
int N,K,stsz[MN],ans=INT_MAX;
set<pii> adj[MN],minlen;

void find_stsz(int u, int p) {
  stsz[u] = 1;
  for(auto [v, l] : adj[u]) {
    if(v == p) continue;
    find_stsz(v, u);
    stsz[u] += stsz[v];
  }
}
int find_centroid(int u, int p, int root) {
  for(auto [v, l] : adj[u]) {
    if(v == p) continue;
    if(stsz[v] > stsz[root]/2) return find_centroid(v, u, root);
  }
  return u;
}

void dfs_upd(int u, int p, int dist, int dep) {
  if(dist > K) return;
  auto it = minlen.lower_bound(pii(dist,0));
  if(it == minlen.end() || (*it).first != dist) minlen.insert(pii(dist,dep));
  else if((*it).second > dep) {
    minlen.erase(it);
    minlen.insert(pii(dist,dep));
  }

  for(auto [v, l] : adj[u]) {
    if(v == p) continue;
    dfs_upd(v, u, dist+l, dep+1);
  }
}
void dfs_search(int u, int p, int dist, int dep) {
  if(dist > K) return;
  auto it = minlen.lower_bound(pii(K-dist,0));
  if(it != minlen.end() && (*it).first == K-dist) ans = min(ans, (*it).second+dep);
  for(auto [v, l] : adj[u]) {
    if(v == p) continue;
    dfs_search(v, u, dist+l, dep+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) {
    adj[H[i][0]].insert(pii(H[i][1], L[i]));
    adj[H[i][1]].insert(pii(H[i][0], L[i]));
  }

  queue<int> q;
  q.push(0);
  while(!q.empty()) {
    int u = q.front();
    q.pop();
    minlen.clear();
    minlen.insert(pii(0,0));

    find_stsz(u, -1);
    int cen = find_centroid(u, -1, u);

    for(auto [v, l] : adj[cen]) {
      dfs_search(v, cen, l, 1);
      dfs_upd(v, cen, l, 1);

      adj[v].erase(pii(cen, l));
      q.push(v);
    }
  }

  return (ans==INT_MAX?-1:ans);
}

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