Submission #938542

#	Time	Username	Problem	Language	Result	Execution time	Memory
938542		duckindog	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
#include "race.h"
#endif

const int N = 200'000 + 10;
vector<pair<int, int>> ad[N];

namespace sub1 {
  int d[N];
  int solve(int n, int k, vector<int>& l) { 
    for (int i = 1; i <= n; ++i) d[i] = d[i - 1] + l[i - 1];
    int answer = 1e7;
    for (int i = 1; i <= n; ++i) 
      for (int j = i; j <= n; ++j) 
        if (d[j] - d[i - 1] == k) answer = min(answer, j - i + 1);
      
    return answer;
  }

}

namespace sub2 {
  int d[N], dep[N];
  int f[N][10], st[N], ed[N], it;
  void dfs(int u, int pre = 0) { 
    st[u] = ++it;
    for (int i = 1; i <= 9; ++i)
      f[u][i] = f[f[u][i - 1]][i - 1];

    for (const auto& [v, w] : ad[u]) { 
      if (v == pre) continue;
      d[v] = d[u] + w;
      dep[v] = dep[u] + 1;
      f[v][0] = u;
      dfs(v, u);
    }
    ed[u] = it;
  }
  bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
  int lca(int u, int v) { 
    if (anc(u, v)) return u;
    if (anc(v, u)) return v;

    for (int i = 9; i >= 0; --i)
      if (!anc(f[u][i], v)) u = f[u][i];
    return f[u][0];
  }

  int solve(int n, int k) { 
    dfs(0);
    int answer = 1e7;
    for (int i = 0; i < n; ++i) { 
      for (int j = i + 1; j < n; ++j) { 
        int l = lca(i, j);
        int distant = d[i] + d[j] - 2 * d[l], cnt = dep[i] + dep[j] - 2 * dep[l];
        if (distant == k) answer = min(answer, cnt);
      }
    }

    return answer;
  }

}

int best_path(int n, int k, vector<vector<int>> h, vector<int> l) { 
  int sub = 1;
  for (int i = 0; i < n - 1; ++i) { 
    int u = h[i][0], v = h[i][1], w = l[i];
    if (u > v) swap(u, v);
    ad[u].push_back({v, w});
    ad[v].push_back({u, w});
    if (u != i || v != i + 1) sub = 2;
  }
  sub = (n <= 1'000 ? 2 : k <= 100 ? 3 : 4);

  if (sub == 1) return sub1::solve(n, k, l);
  if (sub == 2) return sub2::solve(n, k);
  return -1;
} 

#ifdef LOCAL
int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  int n, k; cin >> n >> k;
  vector<vector<int>> h(n, vector<int>(2));
  vector<int> l(n);
  for (int i = 0; i < n - 1; ++i) cin >> h[i][0] >> h[i][1] >> l[i];
  
  cout << best_path(n, k, h, l);
}
#endif

Compilation message (stderr)

/usr/bin/ld: /tmp/ccTiLU1F.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