Submission #681419

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

race

#include <bits/stdc++.h>
#include "race.h"
// #pragma GCC optimize(3)
using namespace std;
 
#define int long long
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;

const int maxn = 2e5 + 10;
int n, k, sz[maxn];
vector<pair<pii, int>> adj[maxn];
unordered_map<int, int> small, large;
// unordered_set<int> deleted;
bool is_deleted[maxn] = {0};

void init(int v, int p){
    sz[v] = 1;
    for (auto x : adj[v]){
        int u = x.F.F, w = x.F.S, i = x.S;
        if (is_deleted[i]) continue;
        if (u == p) continue;
        init(u, v); sz[v] += sz[u];
    }
}

int get_centroid(int v, int p, int pog){
    for (auto x : adj[v]){
        int u = x.F.F, w = x.F.S, i = x.S;
        if (is_deleted[i]) continue;
        if (u == p) continue;
        if (sz[u] * 2 > pog){
            sz[v] -= sz[u];
            sz[u] += sz[v];
            return get_centroid(u, v, pog);
        }
    }
    return v;
}

void dfs(int v, int p, int h, int cnt){
    if (small.count(h)) small[h] = min(small[h], cnt);
    else small[h] = cnt;
    for (auto x : adj[v]){
        int u = x.F.F, w = x.F.S, i = x.S;
        if (is_deleted[i]) continue;
        if (u == p) continue;
        dfs(u, v, h + w, cnt + 1);
    }
}

int solve(int v){
    v = get_centroid(v, v, sz[v]);
    int re = INF;
    large.clear();
    small.clear();
    large[0] = 0;
    for (auto x : adj[v]){
        int u = x.F.F, w = x.F.S, i = x.S;
        if (is_deleted[i]) continue;
        dfs(u, v, w, 1);
        for (auto bruh : small){
            if (large.count(k - bruh.F)){
                re = min(re, bruh.S + large[k - bruh.F]);
            }
        }
        for (auto bruh : small){
            if (large.count(bruh.F)) large[bruh.F] = min(large[bruh.F], bruh.S);
            else large[bruh.F] = bruh.S;
        }
        small.clear();
    }
    for (auto x : adj[v]){
        int u = x.F.F, w = x.F.S, i = x.S;
        if (is_deleted[i]) continue;
        is_deleted[i] = true;
        re = min(re, solve(u));
    }
    return re;
}

int best_path(int N, int K, int h[][2], int l[]){
    n = N, k = K;
    FOR(i, n - 1){
        adj[h[i][0]].PB({{h[i][1], l[i]}, i});
        adj[h[i][1]].PB({{h[i][0], l[i]}, i});
    }
    init(0, 0);
    int re = solve(0);
    return (re == INF ? -1 : re);
}

// signed main(){
//     NYOOM;
//     int N, K; cin >> N >> K;
//     int H[N - 1][2], L[N - 1];
//     FOR(i, N - 1) cin >> H[i][0] >> H[i][1] >> L[i];
//     cout << best_path(N, K, H, L);
// }

Compilation message (stderr)

race.cpp: In function 'void init(long long int, long long int)':
race.cpp:29:24: warning: unused variable 'w' [-Wunused-variable]
   29 |         int u = x.F.F, w = x.F.S, i = x.S;
      |                        ^
race.cpp: In function 'long long int get_centroid(long long int, long long int, long long int)':
race.cpp:38:24: warning: unused variable 'w' [-Wunused-variable]
   38 |         int u = x.F.F, w = x.F.S, i = x.S;
      |                        ^
race.cpp: In function 'long long int solve(long long int)':
race.cpp:83:24: warning: unused variable 'w' [-Wunused-variable]
   83 |         int u = x.F.F, w = x.F.S, i = x.S;
      |                        ^
/usr/bin/ld: /tmp/cc1OANRp.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