Submission #1261972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261972		hiepsimauhong	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long

const int oo = 1e18;
const int N = 2e5 + 5;

int n, k, mix, ans;
int d = 0;
vector<pair<int,int>> a[N];

struct Centroid{
      int sz[N];
      int high[N], len[N];
      bool cen[N];
      map<int, pair<int,int>> mp;

      void DFS(int u, int par){
            sz[u] = 1;
            for(auto e : a[u]){
                  int v = e.first;
                  if(v == par || cen[v]){
                        continue;
                  }
                  DFS(v, u);
                  sz[u] += sz[v];
            }
      }

      int find_centroid(int u, int par, int mx){
            for(auto e : a[u]){
                  int v = e.first;
                  if(v == par || cen[v]){
                        continue;
                  }
                  if(sz[v] > mx / 2){
                        return find_centroid(v, u, mx);
                  }
            }
            return u;
      }

      void DFS_ANS(int u, int par, bool check){
            if(high[u] > k){
                  return;
            }
            if(check){
                  if(mp[k - high[u]].second != 0){
                        if(mix > mp[k - high[u]].first + len[u]){
                              mix = mp[k - high[u]].first + len[u];
                        }
                  }
            }
            else{
                  auto &x = mp[high[u]];
                  if(x.first > len[u] || x.second == 0){
                        x.first = len[u];
                        x.second = 1;
                  }
                  else if(x.first == len[u]){
                        x.second++;
                  }
            }

            for(auto e : a[u]){
                  int v = e.first, w= e.second;
                  if(v == par || cen[v]){
                        continue;
                  }
                  len[v] = len[u] + 1;
                  high[v] = high[u] + w;
                  DFS_ANS(v, u, check);
            }
      }

      void tree(int u){
            mp.clear();
            DFS(u, -1);
            int centroid = find_centroid(u, -1, sz[u]);

            cen[centroid] = true;
            mp[0].second = 1;
            high[centroid] = len[centroid] = 0;

            for(auto e : a[centroid]){
                  int v = e.first, w = e.second;
                  if(cen[v]) continue;
                  high[v] = w;
                  len[v] = 1;
                  DFS_ANS(v, centroid, 1);
                  DFS_ANS(v, centroid, 0);
            }

            for(auto e : a[centroid]){
                  int v = e.first;
                  if(!cen[v]) tree(v);
            }
      }
};

Centroid Cen;

int best_path(int N, int K, int H[][2], int L[]){
      // reset
      for(int i = 0; i <= N; i++){
            a[i].clear();
            Cen.sz[i] = Cen.high[i] = Cen.len[i] = 0;
            Cen.cen[i] = false;
      }
      n = N; k = K;
      mix = oo;
      ans = 0;

      // build graph (OJ.uz cho input 0-indexed)
      for(int i=0;i<N-1;i++){
            int u = H[i][0];
            int v = H[i][1];
            int c = L[i];
            a[u].push_back({v, c});
            a[v].push_back({u, c});
      }

      Cen.tree(0);

      if(ans == 0) return -1;
      return 2 * ans;
}

Compilation message (stderr)

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