Submission #1171735

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

race

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
#define IS_INF(x)   (std::isinf(x))
#define IS_NAN(x)   (std::isnan(x))
#define fi   first
#define se   second
#define int long long
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define div   ___div
#define prev   ___prev
#define next   ___next
#define left   ___leftc
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
const int MAXN = 2e5 + 5;
const int MVAL = 1e6 + 5;
const int INF = 1e18;
int n, k, Sz[MAXN], cnt[MVAL], mval = 0, ans = INF;
bool del[MAXN];
vector<pair<int, int>> g[MAXN];
int CountChild(int u, int p = -1) {
    Sz[u] = 1;
    for(auto x : g[u]) {
        if(x.first != p && !del[x.first]) {
            Sz[u] += CountChild(x.first, u);
        }
    }
    return Sz[u];
}
int FindCentroid(int u, int p, int n) {
    for(auto x : g[u]) {
        if(x.first != p && !del[x.first] && Sz[x.first] > n / 2) {
            return FindCentroid(x.first, u, n);
        }
    }
    return u;
}
void update(int u, int p, int prefix, int d = 1) {
    if(prefix > k) return;
    mval = max(mval, prefix);
    if(cnt[prefix] == 0 || d < cnt[prefix]) cnt[prefix] = d;
    for(auto x : g[u]) {
        if(x.first != p && !del[x.first]) {
            update(x.first, u, prefix + x.second, d + 1);
        } 
    }
}
void query(int u, int p, int prefix, int d = 1) {
    if(prefix > k) return;
    mval = max(mval, prefix);
    if(prefix == k) ans = min(ans, d);
    else if(cnt[k - prefix]) ans = min(ans, cnt[k - prefix] + d);
    for(auto x : g[u]) {
        if(x.first != p && !del[x.first]) {
            query(x.first, u, prefix + x.second, d + 1);
        }
    }
}
void CentroidDecomposition(int u) {
    int n = CountChild(u);
    int root = FindCentroid(u, -1, n);
    del[root] = true;
    mval = 0;
    for(auto x : g[root]) {
        if(!del[x.first]) {
            query(x.first, root, x.second);
            update(x.first, root, x.second);
        }
    }
    for(int i = 0; i <= mval; i++) cnt[i] = 0;
    for(auto x : g[root]) {
        if(!del[x.first]) CentroidDecomposition(x.first);
    }
}
void loadtree() {
    cin >> n >> k;
    for(int i = 1; i < n; i++) {
        int u, v, l; cin >> u >> v >> l;
        g[u].push_back({v, l});
        g[v].push_back({u, l});
    }
}
signed main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    loadtree();
    CentroidDecomposition(0);
    if(ans == INF) ans = -1;
    cout << ans;
    return 0;
}

// Author: Phung Duc Minh
// Look at my code, my code is so amazing and legit
// Try to be better!

Compilation message (stderr)

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