Submission #697248

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

race

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

#define fr first
#define sc second

typedef long long ll;
const int MAX = 1e6 + 15;
const int INF = 0x3f3f3f3f;

int H[MAX][2], L[MAX];

ll n, k, ans, sub[MAX], f[MAX];
vector<pair<ll, ll>> adj[MAX], update;
vector<ll> fixupdate;
bool removed[MAX];

void dfsInit(int u, int p){
    sub[u] = 1;

    for(auto e : adj[u]){
        int v = e.fr;
        if(v == p || removed[v]) continue;
        dfsInit(v, u);
        sub[u] += sub[v];
    }
}

int findCentroid(ll u, ll p, ll sz){
    for(auto e : adj[u]){
        if(e.fr == p || removed[e.fr]) continue;
        if(sub[e.fr] > sz / 2) 
            return findCentroid(e.fr, u, sz);
    }

    return u;
}

void dfsCalc(ll u, ll p, ll edges, ll length){
    if(length > k) return;

    update.emplace_back(length, edges);
    fixupdate.emplace_back(length);

    for(auto e : adj[u]){
        ll v = e.fr, w = e.sc;
        if(v == p) continue;
        dfsCalc(v, u, edges + 1, length + w);
    }
}

void decompose(ll u){
    dfsInit(u, u);
    ll centroid = findCentroid(u, u, sub[u]);
    removed[centroid] = true;   

    f[0] = 0;

    for(auto e : adj[centroid]){
        if(removed[e.fr]) continue; 
        dfsCalc(e.fr, centroid, 1, e.sc);

        for(auto p : update)
            if(p.fr <= k) ans = min(ans, p.sc + f[k - p.fr]);

        for(auto p : update)
            if(p.fr <= k) f[p.fr] = min(f[p.fr], p.sc);

        update.clear();
    }

    for(auto x : fixupdate) f[x] = INF;
    fixupdate.clear();

    for(auto e : adj[centroid])
        if(!removed[e.fr]) decompose(e.fr);
}

int best_path(int _n, int _k, int h[][2], int l[]){
    n = _n, k = _k;

    for(int i = 0; i < n - 1; i++){
        ll u = h[i][0], v = h[i][1], w = l[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    ans = INF;
    for(int i = 0; i <= k; i++) f[i] = INF;

    decompose(0);

    return (ans == INF ? -1 : ans);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;

    for(int i = 0; i < n - 1; i++)
        cin >> H[i][0] >> H[i][1] >> L[i];

    cout << best_path(n, k, H, L) << '\n';
}

Compilation message (stderr)

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