Submission #834488

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

race

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long
const ll mod = 1e9 + 7;
const ll mxN = 5e5 + 5;
#define MAX_N 500000
vector<vector<pair<ll,ll>>>v;
map<ll,ll>mp[mxN];
ll vis[mxN];
ll n, k;
ll sh[mxN],sha[mxN];
ll ans;
ll p[mxN];
void dfs(ll u){
  vis[u] = 1;
  for(auto ch : v[u]){
    if(!vis[ch.F]){
      dfs(ch.F);
      ll a = u,b = ch.F;
      if(mp[p[a]].size() < mp[p[b]].size()){
        swap(a,b);
      }
      if(b == u){
        // cout<<a<<'\n';
        // for(auto x : mp[p[a]]) {
        //   cout<<x.first + sh[p[a]]<<' '<<x.second<<'\n';
        // }
        // cout<<b<<'\n';
        // for(auto x : mp[p[b]]) {
        //   cout<<x.first + sh[p[b]]<<' '<<x.second<<'\n';
        // }
        for(auto x : mp[p[b]]) {
          if(mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]])
            ans = min(ans, x.second + sha[p[b]] + mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]] + 1);
        }
        for(auto x : mp[p[b]]){
          if(mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]])
            mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]] = min(mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]],x.second - 1 + sha[p[b]]);
          else mp[p[a]][x.first - ch.S + sh[p[b]] - sh[p[a]]] = x.second - 1 + sha[p[b]];
        }
        sh[p[a]] += ch.S;
        sha[p[a]]++;
      }else{
        // cout<<a<<'\n';
        // for(auto x : mp[p[a]]) {
        //   cout<<x.first + sh[p[a]]<<' '<<x.second + sha[p[a]]<<'\n';
        // }
        // cout<<b<<'\n';
        // for(auto x : mp[p[b]]) {
        //   cout<<x.first + sh[p[b]]<<' '<<x.second + sha[p[b]]<<'\n';
        // }
        for(auto x : mp[p[b]]) {
          if(mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]])
            ans = min(ans, x.second + sha[p[b]] + mp[p[a]][k - x.first - sh[p[b]] - sh[p[a]] - ch.S] + sha[p[a]] + 1);
        }
        for(auto x : mp[p[b]]){
          if(mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]])
            mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]] = min(mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]],x.second + 1 + sha[p[b]]);
          else mp[p[a]][x.first + ch.S + sh[p[b]] - sh[p[a]]] = x.second + 1 + sha[p[b]];
        }
      }
      p[b] = p[a];
    }
  }
  mp[p[u]][-sh[p[u]]] = 0;
}
int best_path(ll N, ll K, ll H[][2], ll L[])
{
  n = N;k = K;
  ans = 1e10;
  memset(vis,0,sizeof vis);
  for(ll i = 1;i <= n;i++){
    p[i] = i;
    sh[i] = 0;
    mp[i].clear();
  }
  v.clear();
  v.resize(n + 1);
  for (ll i = 0;i < n - 1;i++){
    v[H[i][0] + 1].push_back({H[i][1] + 1,L[i]});
    v[H[i][1] + 1].push_back({H[i][0] + 1,L[i]});
  }
  dfs(1);
  if(ans == 1e10) ans = -1;
  return ans;
}
//
// static ll N, K;
// static ll H[MAX_N][2];
// static ll L[MAX_N];
// static ll solution;
// inline
// void my_assert(ll e) {if (!e) abort();}
// void read_input()
// {
//   ll i;
//   my_assert(2==scanf("%d %d",&N,&K));
//   for(i=0; i<N-1; i++)
//     my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
// }
//
// main()
// {
//   read_input();
//   best_path(N,K,H,L);
//   cout<<ans;
//   return 0;
// }

Compilation message (stderr)

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