제출 #345088

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
345088		casperwang	경주 (Race) (IOI11_race)	C++14	0 / 100	205 ms	262148 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;

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.resize(N);
  vis.resize(N);
  sze.resize(N);
  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) {
  d.pb(sum, dth);
  for (pii e : path[now]) {
    if (vis[e.ff] || e.ff == par) continue;
    dfs_dis(now, par, 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;
  map <int,int> dis;
  for (pii e : path[r]) {
    if (vis[e.ff] || e.ff == par) continue;
    d.clear();
    dfs_dis(e.ff, r, e.ss, 1);
    for (pii it : d)
      if (dis.count(k-it.ff))
        ans = min(ans, dis[k-it.ff] + 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);
    }
  }
  for (pii e : path[r]) {
    if (vis[e.ff] || e.ff == par) continue;
    solve(e.ff, now);
  }
}

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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57