Submission #650749

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

race

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 5;
const long long INF = 1e18 + 7;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;

vector <pair<int, int>> a[N];
int h[N], e[N], n, k;
int ans = MAXA;
map <int, int> m[N];

void dfs(int u, int par = -1){
    for(pair<int, int> st : a[u]){
        int i = st.first, w = st.second;
        if (i == par) continue;

        e[i] = e[u] + 1;
        h[i] = h[u] + w;

        dfs(i, u);

        if (m[u].empty()){
            swap(m[u], m[i]);
            if (m[u].find(k + h[u]) != m[u].end()) ans = min(ans, m[u][k + h[u]] - e[u]);

            if (m[u].find(h[u]) != m[u].end()) m[u][h[u]] = min(m[u][h[u]], e[u]);
            else m[u][h[u]] = e[u];
        } else {
            for(pair<int, int> st : m[i]){
                int h1 = st.first, e1 = st.second;
                //h1 + x - 2 * h[u] = k

                if (m[u].find(k - h1 + 2 * h[u]) != m[u].end()){
                    ans = min(ans, e1 + m[u][k - h1 + 2 * h[u]] - 2 * e[u]);
                }
            }

            for(pair<int, int> st : m[i]){
                int h1 = st.first, e1 = st.second;

                if (m[u].find(h1) != m[u].end()){
                    m[u][h1] = min(m[u][h1], e1);
                } else m[u][h1] = e1;
            }
        }
    }

    if (m[u].empty()) m[u][h[u]] = e[u];
}

int best_path(int N, int K, int H[][2], int L[]){
    n = N; k = K;
    for(int i = 0; i < N - 1; ++i){
        a[H[i][0]].push_back({H[i][1], L[i]});
        a[H[i][1]].push_back({H[i][0], L[i]});
    }
    for(int i = 0; i < N; ++i){
        sort(a[i].begin(), a[i].end(), [](pair<int, int> v1, pair<int, int> v2){return a[v1.first].size() > a[v2.first].size();});
    }

    dfs(0);

    if (ans == MAXA) return -1;
    else return ans;
}

Compilation message (stderr)

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