Submission #501008

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

race

#include <bits/stdc++.h>
#include "race.h"
#define DEBUG 0
using namespace std;

const int N = 2e5 + 10;
const int INF = 1e9 + 7;

vector <pair <int, int>> adj[N];
int sz[N];
bool visited[N];
map <long long, int> mp;
int ans = INF;

int find_size(int u, int p) {
    sz[u] = 1;
    for(auto [v, w] : adj[u]) {
        if(v == p || visited[v]) {
            continue;
        }

        sz[u] += find_size(v, u);
    }
    return sz[u];
}

int find_centroid(int u, int p, int n) {
    for(auto [v, w] : adj[u]) {
        if(v == p || visited[v]) {
            continue;
        }

        if(sz[v] > n / 2) {
            return find_centroid(v, u, n);
        }
    }
    return u;
}

void dfs(int u, int p, long long total, bool state, int depth, int K) {
    if(state) {
        if(mp.count(total)) {
            mp[total] = min(mp[total], depth);
        }
        else {
            mp[total] = depth;
        }
    }
    else {
        if(mp.count(K - total)) {
            ans = min(ans, depth + mp[K - total]);
        }
    }

    for(auto [v, w] : adj[u]) {
        if(v == p || visited[v]) {
            continue;
        }

        dfs(v, u, total + w, state, depth + 1, K);
    }
}

void centroid(int u, int K) {
    int c = find_centroid(u, -1, find_size(u, -1));
    visited[c] = 1;

    mp.clear();
    for(auto [v, w] : adj[c]) {
        if(visited[v]) {
            continue;
        }

        dfs(v, -1, w, 0, 1, K);
        dfs(v, -1, w, 1, 1, K);
    }

    for(auto [v, w] : adj[c]) {
        if(visited[v]) {
            continue;
        }

        centroid(v, K);
    }
}

int best_path(int N, int K, vector <vector <int>> H, vector <int> L) {
    for(int i = 0; i < N - 1; i++) {
        H[i][0]++, H[i][1]++;
        adj[H[i][0]].emplace_back(H[i][1], L[i]);
        adj[H[i][1]].emplace_back(H[i][0], L[i]);
    }

    centroid(1, K);
    
    if(ans == INF) {
        ans = -1;
    }
    return ans;
}

Compilation message (stderr)

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