제출 #1283120

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

race

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

static const int INF = 1e9;

static int N_, K_;
static vector<vector<pair<int,int>>> g;
static vector<int> sz;
static vector<char> dead;
static int answer;

static void dfs_size(int u, int p){
    sz[u] = 1;
    for (auto [v, w] : g[u]) if (v != p && !dead[v]){
        dfs_size(v, u);
        sz[u] += sz[v];
    }
}
static int find_centroid(int u, int p, int tot){
    for (auto [v, w] : g[u]) if (v != p && !dead[v]){
        if (sz[v] * 2 > tot) return find_centroid(v, u, tot);
    }
    return u;
}

static void collect(int u, int p, int dist, int edges, vector<pair<int,int>>& vec){
    if (dist > K_) return;
    vec.emplace_back(dist, edges);
    for (auto [v, w] : g[u]) if (v != p && !dead[v]){
        collect(v, u, dist + w, edges + 1, vec);
    }
}

static void solve_centroid(int c){
    vector<int> best(K_ + 1, INF);
    best[0] = 0;                

    for (auto [v, w] : g[c]) if (!dead[v]){
        vector<pair<int,int>> buf;
        collect(v, c, w, 1, buf);

        for (auto [d, e] : buf){
            if (d <= K_){
                int need = K_ - d;
                if (best[need] != INF) answer = min(answer, e + best[need]);
            }
        }
        for (auto [d, e] : buf){
            if (d <= K_) best[d] = min(best[d], e);
        }
    }
}

static void decompose(int entry){
    dfs_size(entry, -1);
    int c = find_centroid(entry, -1, sz[entry]);
    dead[c] = 1;

    solve_centroid(c);

    for (auto [v, w] : g[c]) if (!dead[v]){
        decompose(v);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    N_ = N; K_ = K;
    if (K_ == 0) return 0;

    g.assign(N_, {});
    sz.assign(N_, 0);
    dead.assign(N_, 0);
    answer = INF;

    for (int i = 0; i < N_ - 1; ++i){
        int u = H[i][0], v = H[i][1], w = L[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    decompose(0);
    return (answer == INF ? -1 : answer);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K; 
    if (!(cin >> N >> K)) return 0;
    vector<array<int,2>> H(N - 1);
    vector<int> L(N - 1);
    for (int i = 0; i < N - 1; ++i){
        int u, v, w; 
        cin >> u >> v >> w;     
        H[i] = {u, v};
        L[i] = w;
    }

    static int HH[200000 + 5][2];
    static int LL[200000 + 5];
    for (int i = 0; i < N - 1; ++i){
        HH[i][0] = H[i][0];
        HH[i][1] = H[i][1];
        LL[i]    = L[i];
    }

    cout << best_path(N, K, HH, LL) << '\n';
    return 0;
}

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

/usr/bin/ld: /tmp/ccfgjweH.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccoFgzfR.o:race.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status