Submission #222690

#	Time	Username	Problem	Language	Result	Execution time	Memory
222690		xiaowuc1	Race (IOI11_race)	C++17	21 / 100	3078 ms	18168 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 merge(map<int, int>& dp, map<int, int>& childdp, int w) {
  // query
  if(sz(childdp) < sz(dp)) {
    for(auto out: childdp) {
      int want = k - out.first - w;
      if(dp.count(want)) ret = min(ret, out.second + dp[want] + 1);
    }
  }
  else {
    for(auto out: dp) {
      int want = k - out.first - w;
      if(childdp.count(want)) ret = min(ret, out.second + childdp[want] + 1);
    }
  }
  map<int, int> clean;
  for(auto out: childdp) {
    if(out.first + w <= k) clean[out.first+w] = out.second + 1;
  }
  // merge
  if(sz(dp) < sz(clean)) dp.swap(clean);
  for(auto out: clean) {
    if(!dp.count(out.first)) dp[out.first] = out.second;
    else dp[out.first] = min(dp[out.first], out.second);
  }
}
void dfsforans(int curr, int par, map<int, int>& dp) {
  for(pii out: edges[curr]) {
    if(centroidseen[out.first] || par == out.first) continue;
    map<int, int> childdp;
    dfsforans(out.first, curr, childdp);
    if(childdp.count(k)) ret = min(ret, childdp[k]);
    merge(dp, childdp, out.second);
  }
  dp[0] = 0;
}
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;
    dfsforans(curr, -1, dp);
  }
  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: 0 / 22
• Subtask 4: 0 / 57