Submission #963915

#	Time	Username	Problem	Language	Result	Execution time	Memory
963915		zNatsumi	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

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

using namespace std;
const int N = 2e5 + 5, oo = 1e14;
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)];
  }
  void 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));
        }
    cout << (res == oo ? -1 : res) << endl;
  }
}

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;
  }
  void solve(){
    dfs(0);
    cout << (res == oo ? -1 : res) << endl;
  }
}

int32_t main()
{
  cin.tie(0)->sync_with_stdio(0); cout.tie(0);
//  if(fopen("test.inp", "r")){
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
//  }
  cin >> n >> k;
  for(int i = 2; i <= n; i++){
    int u, v, w; cin >> u >> v >> w;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  if(n <= 1000) sub12::solve();
  else sub34::solve();

  return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccuGAyTe.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccBad9mf.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccBad9mf.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status