제출 #963919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
963919		zNatsumi	경주 (Race) (IOI11_race)	C++14	100 / 100	780 ms	36984 KiB

race

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second

using namespace std;
const int N = 2e5 + 5, oo = 1e9;
int n, k;
vector<ii> g[N];

namespace sub12{
  int up[N][20], cnt[N], path[N], res = oo;
  int timer, in[N], out[N];

  void dfs(int u){
    in[u] = ++timer;
    for(int i = 1; i < 20; i++)
      up[u][i] = up[up[u][i-1]][i-1];
    for(auto x : g[u]){
      int v = x.fi, w = x.se;
      if(v == up[u][0]) continue;
      up[v][0] = u;
      cnt[v] = cnt[u] + 1;
      path[v] = path[u] + w;
      dfs(v);
    }
    out[u] = ++timer;
  }
  bool anc(int u, int v){
    return in[u] <= in[v] && out[v] <= out[u];
  }
  int lca(int u, int v){
    if(anc(u, v)) return u;
    if(anc(v, u)) return v;
    for(int i = 19; i >= 0; i--)
      if(!anc(up[u][i], v)) u = up[u][i];
    return up[u][0];
  }
  int dist(int u, int v){
    return path[u] + path[v] - 2*path[lca(u, v)];
  }
  int cal(int u, int v){
    return cnt[u] + cnt[v] - 2*cnt[lca(u, v)];
  }
  int solve(){
    dfs(0);
    int res = oo;
    for(int u = 0; u < n; u++)
      for(int v = u+1; v < n; v++)
        if(dist(u, v) == k){
          res = min(res, cal(u, v));
        }
    return (res == oo ? -1 : res);
  }
}

namespace sub34{
  const int V = 1e6 + 5;
  int child[N], res = oo;
  bool del[N];
  map<int, int> path;

  int cnt_child(int u, int p){
    child[u] = 1;
    for(auto x : g[u]){
      int v = x.fi;
      if(v == p || del[v]) continue;
      child[u] += cnt_child(v, u);
    }
    return child[u];
  }
  int centroid(int u, int p, int sz){
    for(auto x : g[u]){
      int v = x.fi;
      if(v == p || del[v]) continue;
      if(child[v] > sz/2) return centroid(v, u, sz);
    }
    return u;
  }
  void cal(int u, int p, int cnt, int len){
    if(len > k) return;
    if(path.find(k - len) != path.end()) res = min(res, cnt + path[k - len]);
    for(auto x : g[u]){
      int v = x.fi, w = x.se;
      if(v == p || del[v]) continue;
      cal(v, u, cnt + 1, len + w);
    }
    return;
  }
  void upd(int u, int p, int cnt, int len){
    if(len > k) return;
    if(path.find(len) == path.end()) path[len] = cnt;
    else path[len] = min(path[len], cnt);

    for(auto x : g[u]){
      int v = x.fi, w = x.se;
      if(v == p || del[v]) continue;
      upd(v, u, cnt + 1, len + w);
    }
  }
  void dfs(int u){
    int sz = cnt_child(u, u);
    u = centroid(u, u, sz);
    del[u] = true;

    path.clear();
    path[0] = 0;
    for(auto x : g[u]){
      int v = x.fi, w = x.se;
      if(del[v]) continue;
      cal(v, u, 1, w);
      upd(v, u, 1, w);
    }
    for(auto x : g[u]){
      int v = x.fi;
      if(del[v]) continue;
      dfs(v);
    }
    return;
  }
  int solve(){
    dfs(0);
    return (res == oo ? -1 : res);
  }
}

int best_path(int _n, int _k, int h[][2], int l[]){
  n = _n;
  k = _k;
  for(int i = 0; i < n-1; i++){
    int u = h[i][0], v = h[i][1], w = l[i];
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  if(n <= 1000) return sub12::solve();
  else return sub34::solve();
}

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