제출 #1341702

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

race

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define BlueCrowner ios_base::sync_with_stdio(0); cin.tie(0);

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

struct Edge {
    int to, weight;
};

vector<Edge> g[MAXN];
bool rem[MAXN];
int sz[MAXN], min_edges[MAXK];
int n, k, ans = INF;

vector<int> modified_weights;

int get_subtree_size(int u, int p) {
    sz[u] = 1;
    for (auto& edge : g[u]) {
        if (edge.to != p && !rem[edge.to]) 
            sz[u] += get_subtree_size(edge.to, u);
    }
    return sz[u];
}

int get_centroid(int u, int p, int total_sz) {
    for (auto& edge : g[u]) {
        if (edge.to != p && !rem[edge.to] && sz[edge.to] > total_sz / 2)
            return get_centroid(edge.to, u, total_sz);
    }
    return u;
}

void get_paths(int u, int p, int depth, int weight, vector<pair<int, int>>& paths) {
    if (weight > k) return;
    paths.push_back({weight, depth});
    for (auto& edge : g[u]) {
        if (edge.to != p && !rem[edge.to]) {
            get_paths(edge.to, u, depth + 1, weight + edge.weight, paths);
        }
    }
}

void decompose(int u) {
    int total_s = get_subtree_size(u, -1);
    int centroid = get_centroid(u, -1, total_s);
    rem[centroid] = true;

    modified_weights.clear();
    min_edges[0] = 0;
    modified_weights.push_back(0);

    for (auto& edge : g[centroid]) {
        if (!rem[edge.to]) {
            vector<pair<int, int>> subtree_paths;
            get_paths(edge.to, centroid, 1, edge.weight, subtree_paths);

            for (auto& path : subtree_paths) {
                if (k >= path.ff) {
                    ans = min(ans, path.ss + min_edges[k - path.ff]);
                }
            }

            for (auto& path : subtree_paths) {
                if (path.ss < min_edges[path.ff]) {
                    if (min_edges[path.ff] == INF) modified_weights.push_back(path.ff);
                    min_edges[path.ff] = path.ss;
                }
            }
        }
    }

    for (int w : modified_weights) min_edges[w] = INF;

    for (auto& edge : g[centroid]) {
        if (!rem[edge.to]) decompose(edge.to);
    }
}

int main() {
    BlueCrowner;
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    fill(min_edges, min_edges + MAXK, INF);
    decompose(0);

    if (ans >= n) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}

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

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