Submission #36296

#	Time	Username	Problem	Language	Result	Execution time	Memory
36296		funcsr	Race (IOI11_race)	C++14	100 / 100	1976 ms	95280 KiB

race

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <cassert>
#include "race.h"
using namespace std;
#define INF 1145141919
#define rep(i, n) for (int i=0; i<(n); i++)
#define _1 first
#define _2 second
#define all(x) x.begin(), x.end()
#define pb push_back
typedef pair<int, int> P;
inline void chmin(int &x, int v) { if (x > v) x = v; }

int N, K;
int ans;
bool dead[200000];
vector<P> G[200000];

multiset<int> C[1000001];
void merge(vector<vector<P> > vs) {
  if (vs.empty()) return;
  for (vector<P> &ps : vs) for (P &x : ps) {
    if (x._1 == K) chmin(ans, x._2);
  }
  if (vs.size() < 2) return;
  //for (auto &p : vs) { cout<<"{"; for (P &x : p)cout<<"("<<x._1<<","<<x._2<<"),"; cout<<"},"; } cout<<"\n";

  for (vector<P> &ps : vs) for (P &x : ps) C[x._1].insert(x._2);
  for (vector<P> &ps : vs) {
    for (P &x : ps) C[x._1].erase(C[x._1].find(x._2));
    for (P &x : ps) {
      if (!C[K-x._1].empty()) chmin(ans, x._2 + *C[K-x._1].begin());
    }
    for (P &x : ps) C[x._1].insert(x._2);
  }
  for (vector<P> &ps : vs) for (P &x : ps) C[x._1].clear();
}

int sz[200000];
int all;
void dfs2(int x, int p) {
  sz[x] = 1;
  for (P pp : G[x]) {
    int t = pp._1;
    if (dead[t] || t == p) continue;
    dfs2(t, x);
    sz[x] += sz[t];
  }
}
P dfs3(int x, int p) {
  P mp = P(INF, -1);
  int mc = all-sz[x];
  for (P pp : G[x]) {
    int t = pp._1;
    if (dead[t] || t == p) continue;
    mp = min(mp, dfs3(t, x));
    mc = max(mc, sz[t]);
  }
  return min(mp, P(mc, x));
}

int centroid(int s) {
  dfs2(s, -1);
  all = sz[s];
  return dfs3(s, -1)._2;
}

void dfs(int x, int p, int d, int r, vector<P> &ret) {
  if (d > K) return;
  ret.pb(P(d, r));
  for (P pp : G[x]) {
    int t = pp._1;
    if (dead[t] || t == p) continue;
    dfs(t, x, d+pp._2, r+1, ret);
  }
}

vector<P> solve(int s) {
  vector<P> ret;
  dfs(s, -1, 0, 0, ret);

  int g = centroid(s);
  dead[g] = true;
  vector<vector<P> > vs;
  for (P pp : G[g]) {
    int t = pp._1;
    if (dead[t]) continue;
    vector<P> cs = solve(t);
    vector<P> new_cs;
    for (P x : cs) if (x._1+pp._2 <= K) new_cs.pb(P(x._1+pp._2, x._2+1));
    vs.pb(new_cs);
  }
  merge(vs);
  return ret;
}

int best_path(int n, int k, int H[][2], int L[]) {
  N = n, K = k;
  rep(i, N) G[i].clear(), dead[i] = false;
  rep(i, 1000001) C[i].clear();
  rep(i, N-1) {
    G[H[i][0]].pb(P(H[i][1], L[i]));
    G[H[i][1]].pb(P(H[i][0], L[i]));
  }
  ans = INF;

  int g = centroid(0);
  dead[g] = true;
  vector<vector<P> > vs;
  for (P pp : G[g]) {
    int t = pp._1;
    if (dead[t]) continue;
    vector<P> cs = solve(t);
    vector<P> new_cs;
    for (P x : cs) if (x._1+pp._2 <= K) new_cs.pb(P(x._1+pp._2, x._2+1));
    vs.pb(new_cs);
  }
  merge(vs);
  if (ans == INF) ans = -1;
  return ans;
}

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