제출 #1323994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1323994		sh_qaxxorov_571	은행 (IZhO14_bank)	C++20	컴파일 에러	0 ms	0 KiB

bank

#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200005;
const int MAXK = 1000005;
const int INF = 1e9;

vector<pair<int, int>> adj[MAXN];
int sz[MAXN], deleted[MAXN];
int min_depth[MAXK];
int ans = INF;
int N, K;

int get_sz(int u, int p) {
    sz[u] = 1;
    for (auto& edge : adj[u]) {
        if (edge.first != p && !deleted[edge.first])
            sz[u] += get_sz(edge.first, u);
    }
    return sz[u];
}

int get_centroid(int u, int p, int total) {
    for (auto& edge : adj[u]) {
        if (edge.first != p && !deleted[edge.first] && sz[edge.first] > total / 2)
            return get_centroid(edge.first, u, total);
    }
    return u;
}

vector<pair<int, int>> current_paths;

void get_paths(int u, int p, int d, int dep) {
    if (d > K) return;
    current_paths.push_back({d, dep});
    if (min_depth[K - d] != INF) ans = min(ans, dep + min_depth[K - d]);

    for (auto& edge : adj[u]) {
        if (edge.first != p && !deleted[edge.first])
            get_paths(edge.first, u, d + edge.second, dep + 1);
    }
}

void decompose(int u) {
    int centroid = get_centroid(u, -1, get_sz(u, -1));
    deleted[centroid] = 1;
    min_depth[0] = 0;
    vector<int> updated;
    updated.push_back(0);

    for (auto& edge : adj[centroid]) {
        if (!deleted[edge.first]) {
            current_paths.clear();
            get_paths(edge.first, centroid, edge.second, 1);
            for (auto& p : current_paths) {
                min_depth[p.first] = min(min_depth[p.first], p.second);
                updated.push_back(p.first);
            }
        }
    }

    for (int idx : updated) min_depth[idx] = INF;
    for (auto& edge : adj[centroid]) {
        if (!deleted[edge.first]) decompose(edge.first);
    }
}

int best_path(int n, int k, int h[][2], int l[]) {
    N = n; K = k;
    for (int i = 0; i < N - 1; i++) {
        adj[h[i][0]].push_back({h[i][1], l[i]});
        adj[h[i][1]].push_back({h[i][0], l[i]});
    }
    fill(min_depth, min_depth + MAXK, INF);
    decompose(0);
    return (ans >= INF ? -1 : ans);
}

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

/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/13/../../../x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x1b): undefined reference to `main'
collect2: error: ld returned 1 exit status