Submission #1099645

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1099645	2024-10-11T22:54:48 Z	hiensumi	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

#include <bits/stdc++.h>
using namespace std;
#define fod(i,a,b) for(int i = (int) (a); i <= (int) (b); i++)
#define fok(i,a,b) for(int i = (int) (a); i >= (int) (b); i--)
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define el '\n'
#define ve vector
#define vi ve<int>
#define vll ve<ll>
#define mask(a) (1LL<<(a))
#define BIT(msk,i) (msk>>(i)&1LL)
using namespace std;
template <class T> bool mini(T &a, T b){ return (a > (b)) ? a = (b), 1 : 0; }
template <class T> bool maxi(T &a, T b){ return (a < (b)) ? a = (b), 1 : 0; }
#define name "lqdrace"

int n, k;

ve <ve<pii>> g;

const int N = 2e5;

bool del[N + 5];
int sz[N + 5];

void find_size(int u, int p){
    sz[u] = 1;
    for(pii who : g[u]) if(who.fi != p and !del[who.fi]) find_size(who.fi, u), sz[u] += sz[who.fi];
}

int root_size;
int find_cent(int u, int p){
    for(pii who : g[u]) if(who.fi != p and !del[who.fi] and 2 * sz[who.fi] > root_size) return find_cent(who.fi, u);
    return u;
}

int mn = 1e9;
ll res = 0;
int f[N + 5], h[N + 5];

void dfs_calc(int u, int p){
    if(f[u] > k) return;
    for(pii who : g[u]) if(!del[who.fi] and who.fi != p){
        f[who.fi] = f[u] + who.se;
        h[who.fi] = h[u] + 1;
        dfs_calc(who.fi, u);
    }
}

unordered_map <int, int> cnt;
unordered_map <int, int> val;

int sz_tree = 0;
pii tree[N + 5];
void dfs_tree(int u, int p){
    tree[++sz_tree] = mp(f[u], h[u]);

    for(pii who : g[u]) if(!del[who.fi] and who.fi != p){
        if(f[u] + who.se <= k) dfs_tree(who.fi, u);
    }

}

void solve_tree(int r){
//    cerr << r << el;
    cnt.clear();
    f[r] = 0;
    h[r] = 0;
    dfs_calc(r, 0);

    cnt[0]++;
    val[0] = 0;

    for(pii who : g[r]) if(!del[who.fi]){
        int v = who.fi;

        sz_tree = 0;
        dfs_tree(v, r);

        fod(i,1,sz_tree){
            int len = k - tree[i].fi;

            if(val.find(len) == val.end()) continue;

            if(mini(mn, val[len] + tree[i].se)){
                res = 1;
            }
            else if(mn == val[len] + tree[i].se){
                res += cnt[len];
            }
        }

        fod(i,1,sz_tree){
            if(val.find(tree[i].fi) == val.end()) val[tree[i].fi] = tree[i].se, cnt[tree[i].fi] = 1;
            else{
                if(mini(val[tree[i].fi], tree[i].se)) cnt[tree[i].fi] = 1;
                else if(val[tree[i].fi] == tree[i].se) cnt[tree[i].fi]++;
            }
        }
    }

}

void dec(int u){
    find_size(u, 0);
    root_size = sz[u];
    int c = find_cent(u, 0);
    del[c] = 1;

    solve_tree(c);

    for(pii who : g[c]) if(!del[who.fi]) dec(who.fi);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
  
    cin >> n >> k;
    {
        g.resize(n + 1);
        int u, v, l;
        fod(i,1,n-1){
            cin >> u >> v >> l;
            u++; v++;
            g[u].pb(mp(v, l));
            g[v].pb(mp(u, l));
        }
    }

    dec(1);

    if(!res) return cout << -1, 0;

    cout << mn;

    return 0;
}

Compilation message

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