Submission #1086520

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1086520	2024-09-10T23:05:52 Z	vjudge1	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

race

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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define rep(i,j,k) for (int i = j; i < (k); i++)
#define in(mp, v) (mp.find(v) != mp.end())
#define smx(a, b) a = max(a, b)
#define smn(a, b) a = min(a, b)
#define pb push_back

const ll MOD = 1e9 + 7;
const ld EPS = 1e-9;

struct decomp {
    vector<vi> adj;
    vector<vector<pair<int, ll>>> adjw;
    vector<bool> r;
    vi s, cpar;
    decomp(int n): adj(n+1), adjw(n+1), r(n+1), s(n+1), cpar(n+1) {}
    int dfs(int n, int p = 0) {
        s[n] = 1;
        for (int x : adj[n])
            if (x != p && !r[x]) s[n] += dfs(x, n);
        return s[n];
    }
    int get_centroid(int n, int ms,
                    int p = 0)
    {
        for (int x : adj[n])
            if (x != p && !r[x])
                if (s[x] * 2 > ms) return get_centroid(x, ms, n);
        return n;
    }

    vector<int> vis, best;
    int dfs2(int x, int p, int C, int k, int d, vector<pii> &res) {
        if (k < 0) return MOD;
        int ans = MOD;
        if (vis[k] == C) smn(ans, best[k]+d);
        res.pb({k, d});
        for (auto &[v, w] : adjw[x]) {
            if (v == p || v == C) continue;
            smn(ans, dfs2(v, x, C, k-w, d+1, res));
        }
        return ans;
    }

    int centroid(int k, int n = 1, int p = 0) {
        int C = get_centroid(n, dfs(n));
        cpar[C] = p;
        int ans = MOD;
        for (auto &[v, w] : adjw[C]) {
            vector<pii> res;
            smn(ans, dfs2(v, C, C, k-w, 1, res));
            for (auto &[nk, nd] : res) {
                nk = k-nk;
                if (vis[nk] != C || best[nk] > nd) {
                    vis[nk] = C;
                    best[nk] = nd;
                }
            }
        }
        r[C] = 1;
        for (int x : adj[C]) 
            if (!r[x]) smn(ans, centroid(k, x, C));
        return ans;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, k; cin >> n >> k;
    decomp d(n);
    rep(i, 0, n-1) {
        int u, v; ll w; cin >> u >> v >> w; u++; v++;
        d.adj[u].pb(v); d.adj[v].pb(u);
        d.adjw[u].pb({v, w}); d.adjw[v].pb({u, w});
    }
    d.vis.resize(k+1, -1);
    d.best = vi(k+1, MOD);
    d.best[0] = 0;
    cout << d.centroid(k) << '\n';
}

Compilation message

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