Submission #1212936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212936		luis_aqm	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define tt tuple<int,int,int>
#define NMAX 200005
#define MOD 1000000007
#define INF 1e18
#define matriz vector<vector<int>>
#define faster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

vector<pii> g[NMAX];
int sz[NMAX];
map<int,int> best, temp;
bitset<NMAX> exc;

int DFS(int v, int pai) {
    sz[v] = 1;

    for(auto [it, d] : g[v]) {
        if(it == pai || exc[it]) continue;

        sz[v] += DFS(it, v);
    }

    return sz[v];
}

int centroid(int v, int pai, int n) {
    for(auto [it, d] : g[v]) {
        if(it == pai || exc[it]) continue;

        if(sz[it] * 2 > n) 
            return centroid(it, v, n);
    }

    return v;
}

void DFS2(int v, int pai, int dist, int nvl, int k) {
    if(dist > k) return;
    if(!temp.count(dist) || temp[dist] > nvl) 
        temp[dist] = nvl;

    for(auto [it, d] : g[v]) {
        if(it == pai || exc[it]) continue;
        DFS2(it, v, dist+d, nvl+1, k);
    }
}

int solve(int v, int k) {
    DFS(v, -1);

    int c = centroid(v, -1, sz[v]);

    int resp = INF;
    best.clear();
    for(auto [it, d] : g[c]) {
        if(exc[it]) continue;

        temp.clear();

        DFS2(it, c, d, 1, k);

        for(auto [dist, nvl] : temp) {
            if(dist == k || best.count(k-dist)) {
                resp = min(resp, nvl+best[k-dist]);
            }
        }
        for(auto [dist, nvl] : temp) {
            if(!best.count(dist) || nvl < best[dist])
                best[dist] = nvl;
        }
    }

    exc.set(c);
    for(auto [it, d] : g[c]) {
        if(exc[it]) continue;

        resp = min(resp, solve(it, k));
    }

    return resp;
}

int32_t main() { faster
    int n, k;
    cin>>n>>k;

    for(int i = 1; i < n; i++) {
        int a, b, c;
        cin>>a>>b>>c;

        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }

    int resp = solve(0, k);
    if(resp == INF) cout<<"-1\n";
    else cout<<resp<<"\n";
}

Compilation message (stderr)

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