Submission #1245154

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

race

// The capital, vodka, the Soviet bear!
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define fi first
#define se second
void maxi (ll &x, ll y) {x = max (x, y);}
void mini (ll &x, ll y) {x = min (x, y);}

const ll maxN = 2e5 + 5, inf64 = 1e18, maxA = 1e6 + 5;

ll n, k, sz [maxN], f [maxA], ans;
bool del [maxN];
vector <ll> vec;
vector <pll> adj [maxN];

ll dfs (ll x, ll par) {
    sz [x] = 1;
    for (pll i : adj [x]) if (!del [i. fi] && i. fi != par) {
        sz [x] += dfs (i. fi, x);
    }
    return sz [x];
}

ll finCen (ll x, ll par, ll cnt) {
    for (pll i : adj [x]) if (!del [i. fi] && i. fi != par) {
        if (sz [i. fi] * 2 >= cnt) return finCen (i. fi, x, cnt);
    }
    return x;
}

void get (ll x, ll par, ll dis, ll numNode) {
    if (k >= dis) mini (ans, f [k - dis] + numNode);
//    cerr << k - dis << ' ' << f [k - dis] + numNode << '\n';
    for (pll i : adj [x]) if (!del [i. fi] && i. fi != par) {
        get (i. fi, x, dis + i. se, numNode + 1);
    }
}

void update (ll x, ll par, ll dis, ll numNode) {
    mini (f [dis], numNode);
    //cerr << dis << ' ' << numNode << '\n';
    vec. push_back (dis);
    for (pll i : adj [x]) if (!del [i. fi] && i. fi != par) {
        update (i. fi, x, dis + i. se, numNode + 1);
    }
}

void build (ll x) {
    ll cnt = dfs (x, -1);
    ll cen = finCen (x, -1, cnt);
    vec. clear ();
    del [cen] = 1;
    for (pll i : adj [cen]) if (!del [i. fi]) {
        get (i. fi, cen, i. se, 1);
        update (i. fi, cen, i. se, 1);
    }
//    cerr << cen << '\n';
//    for (int i = 0; i < 5; i ++) cerr << f [i] << ' ';
//    cerr << '\n';
    for (ll i : vec) f [i] = inf64;
    for (pll i : adj [cen]) if (!del [i. fi]) build (i. fi);
}

ll best_path (int N, int K, int H [] [2], int L []) {
    n = N; k = K;
//    cerr << n << ' ' << k << '\n';
    for (int i = 0, u, v, w; i < n - 1; i ++) {
        u = H [i] [0];
        v = H [i] [1];
        w = L [i];
        adj [u]. push_back ({v, w});
        adj [v]. push_back ({u, w});
//        cerr << u << ' ' << v << ' ' << w << '\n';
    }
//    for (int i = 0; i < n; i ++) {
//        for (pll j : adj [i]) cerr << "(" << j. fi << ',' << j. se << "),";
//        cerr << '\n';
//    }
    ans = inf64;
    for (ll &i : f) i = inf64;
    f [0] = 0;
    build (0);
    if (ans >= inf64) return -1;
    return ans;
}

// int main () {
//     ios::sync_with_stdio (0);
//     cin. tie (0);
//     cout. tie (0);
//     #define task "untitled1"
//     if (fopen (task".inp", "r")) {
//         freopen (task".inp", "r", stdin);
//         freopen (task".out", "w", stdout);
//     }
//     int N, K;
//     cin >> N >> K;
//     int H [N] [2];
//     int L [N];
//     for (int i = 0; i < N - 1; i ++) cin >> H [i] [0] >> H [i] [1];
//     for (int i = 0; i < N - 1; i ++) cin >> L [i];
// //    cerr << N << ' ' << K << '\n';
// //    for (int i = 0; i < N - 1; i ++) cerr << H [i] [0] << ' ' <<  H [i] [1] << '\n';
// //    for (int i = 0; i < N - 1; i ++) cerr << L [i] << ' ';
//     cout << best_path (N, K, H, L) << '\n';
// }

Compilation message (stderr)

race.cpp:67:4: error: ambiguating new declaration of 'll best_path(int, int, int (*)[2], int*)'
   67 | ll best_path (int N, int K, int H [] [2], int L []) {
      |    ^~~~~~~~~
In file included from race.cpp:2:
race.h:1:5: note: old declaration 'int best_path(int, int, int (*)[2], int*)'
    1 | int best_path(int N, int K, int H[][2], int L[]);
      |     ^~~~~~~~~