Submission #789094

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

race

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;

double startTime = clock();
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

int n, k;
int ans = inf;
int tot = 0, cur = 0;
array<int, 3> dis[N];
multiset<int> st[N];

struct CD{
    int n;
    vector<vector<pii>> g;
    vector<int> par, sz;
    vector<bool> vis;
    
    CD(){}
    CD(int n){
        init(n);
    }

    void init(int n){
        this->n = n;
        g.assign(n+1, {});
        par.assign(n+1, 0);
        sz.assign(n+1, 0);
        vis.assign(n+1, 0);
    }
    
    void addEdge(int x, int y, int w){
        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }
    
    void dfs(int i, int f){
        sz[i] = 1;
        for(auto [j, w] : g[i]){
            if(j == f || vis[j]) continue;
            dfs(j, i);
            sz[i] += sz[j];
        }
    }

    int getCentroid(int i, int f, int n){
        for(auto [j, w] : g[i]){
            if(j == f || vis[j]) continue;
            if(sz[j] * 2 > n) return getCentroid(j, i, n);
        }
        return i;
    }
    
    void dfs2(int i, int f, int w, int len, int mark){
        if(w > k) return;
        dis[++tot] = {w, len, mark};
        for(auto [j, wj] : g[i]){
            if(j == f || vis[j]) continue;
            dfs2(j, i, w+wj, len+1, mark);
        }
        
    }

    void work(int i, int f = 0){
        dfs(i, f);
        int cen = getCentroid(i, f, sz[i]);
        vis[cen] = 1;
        par[cen] = f;

        tot = cur = 0;
        for(auto [j, w] : g[cen]){
            if(j == f || vis[j]) continue;
            dfs2(j, i, w, 1, ++cur);
        }

        st[0] = {0};
        for(int j=1; j<=tot; j++){
            st[dis[j][0]].insert(dis[j][1]);
        }
        int x = 1, y = 1;
        for(int j=1; j<=cur; j++){
            while(x <= tot && dis[x][2] == j){
                st[dis[x][0]].erase(st[dis[x][0]].find(dis[x][1]));
                x++;
            }
            while(y <= tot && dis[y][2] == j){
                int tar = k - dis[y][0];
                if(tar >= 0 && tar <= k && !st[tar].empty()){
                    ans = min(ans, dis[y][1] + *st[tar].begin());
                }
                y++;
            }
        }
        
        for(auto [j, w] : g[cen]){
            if(vis[j]) continue;
            work(j, cen);
        }
    }
};

void solve(){
    cin >> n >> k;
    CD cent(n);
    for(int i=1; i<n; i++){
        int x, y, w; cin >> x >> y >> w;
        x++; y++;
        cent.addEdge(x, y, w);
    }
    
    memset(dis, 0, sizeof dis);
    for(int i=1; i<=n; i++) st[i].clear();

    cent.work(1, 0);
    cout << (ans == inf ? -1 : ans) << endl;
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
   // freopen("output.txt", "w", stdout);

    int t = 1;
    //cin >> t;
    while(t--)
    solve();

    return 0;
}

Compilation message (stderr)

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