Submission #569073

#	Time	Username	Problem	Language	Result	Execution time	Memory
569073		eltu0815	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
#define INF 987654321
#define MAX 200005
#define LMAX 1000005

using namespace std;

int N, K;
int sz[MAX], depth[LMAX];
bool visited[MAX];
vector<pair<int, int> > graph[MAX];

int getSize(int node, int parent = -1) {
    sz[node] = 1;
    for(auto v : graph[node]) {
        if(v.first != parent && !visited[v.first]) sz[node] += getSize(v.first, node);
    }
    
    return sz[node];
}

int getCent(int node, int parent, int cap) {
    for(auto v : graph[node]) {
        if(v.first != parent && !visited[v.first] && sz[v.first] * 2 > cap) return getCent(v.first, node, cap);
    }
    return node;
}

void getDepth(int node, int parent, int dep, int len) {
    if(len > LMAX) return; 
    depth[len] = min(depth[len], dep);
    
    for(auto v : graph[node]) {
        if(visited[v.first] || v.first == parent) continue;
        getDepth(v.first, node, dep + 1, len + v.second);
    }
    
    return;
}

int best_path(int node, int parent, int len, int cap) {
    getSize(node, parent);
    int cent = getCent(node, parent, cap);
    
    fill(depth, depth + LMAX, INF);
    getDepth(cent, -1, 0, 0);
    getSize(cent, parent);
    
    visited[cent] = true;
    
    int ret = INF;
    for(int i = 0; i <= len / 2; ++i) {
        ret = min(ret, depth[i] + depth[len - i]);
    }
    
    for(auto v : graph[cent]) {
        if(visited[v.first]) continue;
        ret = min(ret, best_path(v.first, cent, len, sz[v.first]));
    }
    
    return ret;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N >> K;
    for(int i = 0; i < N - 1; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        graph[a].push_back({b, w});
        graph[b].push_back({a, w});
    }
    
    int ans = best_path(0, -1, K, N);
    if(ans == INF) cout << -1;
    else cout << ans;
    
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccGpCUMk.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc95kP7k.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc95kP7k.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