제출 #1184584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184584		colonelsven	경주 (Race) (IOI11_race)	C++20	컴파일 에러	0 ms	0 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e5 + 10;
constexpr int K = 1e6 + 10;
constexpr int INF = 1e9 + 10;

struct edge {
    int v, c;
};

vector<edge> adj[N] = {};
bool isRemoved[N] = {};
int d[N] = {};
int minPath[N] = {};
int lastUpdated[N] = {};

int curcentroid = 1;

int ans = INF;

int n, k;

int dfs(int node, int pr=-1) {
    d[node] = 1;
    for (auto ad : adj[node]) {
        if (ad.v != pr && !isRemoved[ad.v]) {
            d[node] += dfs(ad.v, node);
        }
    }
    return d[node];
}

int getCentroid(int node, int sz, int pr=-1) {
    for (auto ad : adj[node]) {
        if (ad.v != pr && !isRemoved[ad.v] && d[ad.v] > sz / 2) {
            return getCentroid(ad.v, sz, node);
        }
    }
    return node;
}

void update(int node, int cur, int curd, int pr, bool first) {
    if (cur > k || curd >= ans) return;
    if (first) {
        if (lastUpdated[k - cur] == curcentroid) {
            ans = min(ans, curd + minPath[k - cur]);
        }
    }
    else {
        if (lastUpdated[cur] == curcentroid) {
            minPath[cur] = min(curd, minPath[cur]);
        }
        else {
            lastUpdated[cur] = curcentroid;
            minPath[cur] = curd;
        }
    }

    for (auto ad : adj[node]) {
        if (ad.v != pr && !isRemoved[ad.v]) {
            update(ad.v, cur + ad.c, cur + 1, node, first);
        }
    }
}

void solve(int node) {
    curcentroid++;
    int centroid = getCentroid(node, dfs(node));

    lastUpdated[0] = curcentroid;
    minPath[0] = 0;

    for (auto ad : adj[centroid]) {
        if (!isRemoved[ad.v]) {
            update(ad.v, ad.c, 1, centroid, true);
            update(ad.v, ad.c, 1, centroid, false);
        }
    }

    isRemoved[centroid] = true;
    for (auto ad : adj[centroid]) {
        if (!isRemoved[ad.v]) {
            solve(ad.v);
        }
    }
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    solve(0);
    printf("%i\n", ans == INF ? -1 : ans);
}

컴파일 시 표준 에러 (stderr) 메시지

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