Submission #854776

#TimeUsernameProblemLanguageResultExecution timeMemory
854776alex_2008Race (IOI11_race)C++14
Compilation error
0 ms0 KiB
#include "race.h"#include <iostream>#include <algorithm>#include <map>#include <vector>#include <string>#include <unordered_map>#include <cassert>using namespace std;const int MAX_N = 5e5 + 10;bool used[MAX_N];int subtree[MAX_N], dist[MAX_N], height[MAX_N];int h[MAX_N][2], l[MAX_N];int KK;int ans = MAX_N;vector <vector<pair<int, int>>> G;int find_centroid(int v) { int p = -1; int u = v; while (1) { int x = -1; for (auto it : G[u]) { if (it.first == p) continue; if (used[it.first]) continue; if (2 * subtree[it.first] > subtree[v]) { x = it.first; break; } } if (x == -1) return u; p = u; u = x; }}void dfs(int v, int p) { if (p == -1) { dist[v] = 0; height[v] = 0; } subtree[v] = 1; for (auto it : G[v]) { if (it.first == p || used[it.first]) continue; dist[it.first] = min(dist[v] + it.second, KK + 1); height[it.first] = height[v] + 1; dfs(it.first, v); subtree[v] += subtree[it.first]; }}vector <int> vec;void find_vertexes(int v, int p) { vec.push_back(v); for (auto it : G[v]) { if (used[it.first] || it.first == p) continue; find_vertexes(it.first, v); }}void solve(int v) { dfs(v, -1); v = find_centroid(v); dfs(v, -1); vector <vector<int>> u; for (auto it : G[v]) { if (used[it.first]) continue; vec.clear(); find_vertexes(it.first, v); u.push_back(vec); } unordered_map <int, int> mp; for (auto it : u) { for (auto j : it) { if (mp.find(KK - dist[j]) != mp.end()) { ans = min(ans, height[j] + mp[KK - dist[j]]); } } for (auto j : it) { if (mp.find(dist[j]) == mp.end()) { mp[dist[j]] = height[j]; } else mp[dist[j]] = min(mp[dist[j]], height[j]); } } if (mp.find(KK) != mp.end()) { ans = min(ans, mp[KK]); } used[v] = true; for (auto it : G[v]) { if (used[it.first]) continue; solve(it.first); }}int best_path(int N, int K, int H[][2], int L[]) { KK = K; G.resize(N); for (int i = 0; i < N - 1; i++) { G[H[i][0]].push_back({ H[i][1], L[i] }); G[H[i][1]].push_back({ H[i][0], L[i] }); } solve(0); if (ans == MAX_N) return -1; return ans;}//int main() {// int n, k;// cin >> n >> k;// for (int i = 0; i < n - 1; i++) {// cin >> h[i][0] >> h[i][1];// }// for (int i = 0; i < n - 1; i++) {// cin >> l[i];// }// cout << best_path(n, k, h, l) << "\n";//}

Compilation message (stderr)

race.cpp:1:18: warning: extra tokens at end of #include directive
    1 | #include "race.h"#include <iostream>#include <algorithm>#include <map>#include <vector>#include <string>#include <unordered_map>#include <cassert>using namespace std;const int MAX_N = 5e5 + 10;bool used[MAX_N];int subtree[MAX_N], dist[MAX_N], height[MAX_N];int h[MAX_N][2], l[MAX_N];int KK;int ans = MAX_N;vector <vector<pair<int, int>>> G;int find_centroid(int v) { int p = -1; int u = v; while (1) {  int x = -1;  for (auto it : G[u]) {   if (it.first == p) continue;   if (used[it.first]) continue;   if (2 * subtree[it.first] > subtree[v]) {    x = it.first;    break;   }  }  if (x == -1) return u;  p = u;     u = x; }}void dfs(int v, int p) { if (p == -1) {  dist[v] = 0;  height[v] = 0; } subtree[v] = 1; for (auto it : G[v]) {  if (it.first == p || used[it.first]) continue;  dist[it.first] = min(dist[v] + it.second, KK + 1);  height[it.first] = height[v] + 1;  dfs(it.first, v);  subtree[v] += subtree[it.first]; }}vector <int> vec;void find_vertexes(int v, int p) { vec.push_back(v); for (auto it : G[v]) {  if (used[it.first] || it.first == p) continue;  find_vertexes(it.first, v); }}void solve(int v) { dfs(v, -1); v = find_centroid(v); dfs(v, -1); vector <vector<int>> u; for (auto it : G[v]) {  if (used[it.first]) continue;  vec.clear();  find_vertexes(it.first, v);  u.push_back(vec); } unordered_map <int, int> mp; for (auto it : u) {  for (auto j : it) {   if (mp.find(KK - dist[j]) != mp.end()) {    ans = min(ans, height[j] + mp[KK - dist[j]]);   }  }  for (auto j : it) {   if (mp.find(dist[j]) == mp.end()) {    mp[dist[j]] = height[j];   }   else mp[dist[j]] = min(mp[dist[j]], height[j]);  } } if (mp.find(KK) != mp.end()) {  ans = min(ans, mp[KK]); } used[v] = true; for (auto it : G[v]) {  if (used[it.first]) continue;  solve(it.first); }}int best_path(int N, int K, int H[][2], int L[]) { KK = K; G.resize(N); for (int i = 0; i < N - 1; i++) {  G[H[i][0]].push_back({ H[i][1], L[i] });  G[H[i][1]].push_back({ H[i][0], L[i] }); } solve(0); if (ans == MAX_N) return -1; return ans;}//int main() {// int n, k;// cin >> n >> k;// for (int i = 0; i < n - 1; i++) {//  cin >> h[i][0] >> h[i][1];// }// for (int i = 0; i < n - 1; i++) {//  cin >> l[i];// }// cout << best_path(n, k, h, l) << "\n";//}
      |                  ^
/usr/bin/ld: /tmp/ccGVREHQ.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