Submission #672176

#	Time	Username	Problem	Language	Result	Execution time	Memory
672176		vjudge1	경주 (Race) (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

//#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;


#define Baba_Sevawy  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define ld long double
#define el '\n'
#define pi acos(-1)
#define F first
#define S second
#define sz(x) (int)(x).size()

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(gen);
}

const int NN = 2e5 + 5, M = 1e6 + 5, mod = 1e9 + 7, INF  = 2e9;
int siz[NN], k;
ll f[M];
bool vis[NN];
vector<pair<ll, ll>>adj[NN];
vector<pair<ll, ll>>all;
vector<ll>sums;
int dfs_sz(int node, int par){
    siz[node] = 1;
    for(auto i : adj[node]){
        if(i.F == par || vis[i.F]) continue;
        siz[node] += dfs_sz(i.F, node);
    }
    return siz[node];
}
int dfs_centroid(int node, int par, int n){
    for(auto i : adj[node])
        if(i.F != par && !vis[i.F] && siz[i.F] > n / 2) return dfs_centroid(i.F, node, n);
    return node;
}
void dfs_collect(int node, int par, int len, ll sum){
    all.emplace_back(len, sum);
    sums.emplace_back(sum);
    for(auto i : adj[node]){
        if(vis[i.F] || i.F == par) continue;
        dfs_collect(i.F, node, len + 1, sum + i.S);
    }
}
ll build(int node, int par){
    int size = dfs_sz(node, par);
    int centroid = dfs_centroid(node, par, size);
    if(par == -1) par = centroid;
    vis[centroid] = true;
    ll ans = 1e9;
    f[0] = 0;
    for(auto i : adj[centroid]){
        if(vis[i.F]) continue;
        all.clear();
        dfs_collect(i.F, centroid, 1, i.S);
        for(auto j : all)
            if(j.S <= k && f[k - j.S] != -1)
                ans = min(ans, j.F + f[k - j.S]);

        for(auto j : all) {
            if (f[j.S] == -1) f[j.S] = j.F;
            else f[j.S] = min(f[j.S], j.F);
        }
    }
    for(auto &i : sums) if(i < M) f[i] = -1;
    sums.clear();
    for(auto i : adj[centroid]){
        if(vis[i.F]) continue;
        ans = min(ans, build(i.F, centroid));
    }
    return ans;
}

Compilation message (stderr)

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