Submission #222693

#	Time	Username	Problem	Language	Result	Execution time	Memory
222693		xiaowuc1	Race (IOI11_race)	C++17	100 / 100	1447 ms	42872 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef vector<int> vi;
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<vector<ll>> matrix;
typedef pair<ll, ll> pll;

int ret;
int n, k;
vector<pii> edges[200000];
bool centroidseen[200000];
int treesz[200000];

void dfsfromcentroid(int curr, int par, map<int, int>& dp, int dist, int roads) {
  if(dist > k) return;
  if(!dp.count(dist)) dp[dist] = roads;
  else dp[dist] = min(dp[dist], roads);
  for(pii out: edges[curr]) {
    if(centroidseen[out.first] || out.first == par) continue;
    dfsfromcentroid(out.first, curr, dp, dist + out.second, roads + 1);
  }
}
void dfsforsz(int curr, int par) {
  treesz[curr] = 1;
  for(pii out: edges[curr]) {
    int child = out.first;
    if(centroidseen[child] || child == par) continue;
    dfsforsz(child, curr);
    treesz[curr] += treesz[child];
  }
}
void centroiddecomp(int curr) {
  if(centroidseen[curr]) return;
  dfsforsz(curr, -1);
  int totalsz = treesz[curr];
  int centroidpar = -1;
  while(true) {
    int biggestchildsz = -1;
    int biggestchild = -1;
    for(pii out: edges[curr]) {
      int cand = out.first;
      if(centroidseen[cand] || cand == centroidpar) continue;
      if(treesz[cand] > biggestchildsz) {
        biggestchildsz = treesz[cand];
        biggestchild = cand;
      }
    }
    if(2 * biggestchildsz > totalsz) {
      centroidpar = curr;
      curr = biggestchild;
    }
    else {
      break;
    }
  }
  // curr is the centroid
  {
    map<int, int> dp;
    for(pii edge: edges[curr]) {
      if(centroidseen[edge.first]) continue;
      map<int, int> childdp;
      dfsfromcentroid(edge.first, curr, childdp, edge.second, 1);
      for(auto out: childdp) {
        if(out.first == k) ret = min(ret, out.second);
        if(dp.count(k - out.first)) ret = min(ret, out.second + dp[k - out.first]);
      }
      for(auto out: childdp) {
        if(!dp.count(out.first)) dp[out.first] = out.second;
        else dp[out.first] = min(dp[out.first], out.second);
      }
    }
  }
  centroidseen[curr] = true;
  for(pii out: edges[curr]) centroiddecomp(out.first);
}

int best_path(int N, int K, int H[][2], int L[]) {
  n = N;
  k = K;
  ret = n+1;
  for(int i = 0; i < n-1; i++) {
    edges[H[i][0]].emplace_back(H[i][1], L[i]);
    edges[H[i][1]].emplace_back(H[i][0], L[i]);
  }
  centroiddecomp(0);
  if(ret > n) ret = -1;
  return ret;
}

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