Submission #345112

#	Time	Username	Problem	Language	Result	Execution time	Memory
345112		casperwang	Race (IOI11_race)	C++14	100 / 100	1108 ms	40716 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define pb emplace_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 200000;
vector <vector<pii>> path;
vector <bool> vis;
vector <int> sze;
vector <pii> d;
int n;
int ans, k;

void init(int N) {
  path.clear();
  path.resize(N);
  vis.clear();
  vis.resize(N);
  sze.clear();
  sze.resize(N);
  d.clear();
  ans = MAXN;
}

int dfs_sze(int now, int par) {
  sze[now] = 1;
  for (pii e : path[now]) {
    if (vis[e.ff] || e.ff == par) continue;
    sze[now] += dfs_sze(e.ff, now);
  }
  return sze[now];
}

int fnd_cen(int now, int par) {
  for (pii e : path[now]) {
    if (vis[e.ff] || e.ff == par) continue;
    if (sze[e.ff] * 2 > n)
      return fnd_cen(e.ff, now);
  }
  return now;
}

void dfs_dis(int now, int par, int sum, int dth) {
  if (sum > k) return;
  d.pb(sum, dth);
  for (pii e : path[now]) {
    if (vis[e.ff] || e.ff == par) continue;
    dfs_dis(e.ff, now, sum+e.ss, dth+1);
  }
}

void solve(int now, int par) {
  n = dfs_sze(now, -1);
  int r = fnd_cen(now, -1);
  vis[r] = 1;
  unordered_map <int,int> dis;
  for (pii e : path[r]) {
    if (vis[e.ff] || e.ff == par) continue;
    dfs_dis(e.ff, -1, e.ss, 1);
    for (pii it : d) {
      if (dis.count(k-it.ff)) {
        ans = min(ans, dis[k-it.ff] + it.ss);
      } else if (it.ff == k) {
        ans = min(ans, it.ss);
      }
    }
    for (pii it : d) {
      if (!dis.count(it.ff)) {
        dis[it.ff] = it.ss;
       } else {
        dis[it.ff] = min(dis[it.ff], it.ss);
       }
    }
    d.clear();
  }
  dis.clear();
  for (pii e : path[r]) {
    if (vis[e.ff] || e.ff == par) continue;
    solve(e.ff, now);
  }
  return;
}

int best_path(int N, int K, int H[][2], int L[]) {
  init(N);
  k = K;
  for (int i = 0; i < N-1; i++) {
    path[H[i][0]].pb(H[i][1], L[i]);
    path[H[i][1]].pb(H[i][0], L[i]);
  }
  solve(0, -1);
  return ans == MAXN ? -1 : ans;
}

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