Submission #1149939

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

race

#include<bits/stdc++.h>
#define ii pair<int,int>
#define fi first
#define se second
#define int long long
#define task ""
using namespace std;

const int N = 2e5 + 10, mod = 1e9 + 7;
const int oo = 1e18;
int n, k, ans, mi[N], ma_h;
int sz[N], h[N], par[N], root;
bool is_centroid[N];
vector<ii> g[N];

void dfs(int u, int par){
    sz[u] = 1;
    for(ii k : g[u]){
        int v = k.fi, c = k.se;
        if(v == par || is_centroid[v]) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}
int find_centroid(int u, int sz_tree, int par){
    for(ii k : g[u]){
        int v = k.fi, c = k.se;
        if(v != par && !is_centroid[v] && sz[v] > sz_tree/2)
            return find_centroid(v, sz_tree, u);
    }
    return u;
}

void get(int u, int par, int h, int w, int t){
    if(w > k) return;
    if(t == 0)
        ans = min(ans, mi[k - w] + h);
    else
        mi[w] = min(mi[w], h);
    ma_h = max(ma_h, w);
    for(ii k : g[u]){
        int v = k.fi, c = k.se;
        if(v == par || is_centroid[v]) continue;
        get(v, u, h + 1, w + c, t);
    }
}

void build_centroid(int u, int par){
    dfs(u, -1);
    int centroid = find_centroid(u, sz[u], -1);
    // cout << u << ' ' << sz[u] << '\n';
    // cout << u << ' ' << centroid << '\n';
    if(root == 0) root = centroid;
    is_centroid[centroid] = 1;
    for(ii k : g[centroid]){
        int v = k.fi, c = k.se;
        if(!is_centroid[v]){
            get(v, centroid, 1, c, 0);
            get(v, centroid, 1, c, 1);
        }
    }
    for(int i = 1; i <= ma_h; i++) mi[i] = oo;
    for(ii k : g[centroid]){
        int v = k.fi;
        if(!is_centroid[v]) build_centroid(v, u);
    }
}
int best_path(int N, int K, int H[][2], int L[]){
    n = N; k = K;
    for(int i = 0; i < n - 1; i++){
        g[H[i][0] + 1].push_back(ii(H[i][1] + 1, L[i]));
        g[H[i][1] + 1].push_back(ii(H[i][0] + 1, L[i]));
    }
    // memset(is_centroid, 0, sizeof(is_centroid));
    for(int i = 1; i <= k; i++)
        mi[i] = oo;
    ans = oo;
    build_centroid(1, -1);
    return (ans == oo ? -1 : ans);
}
main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if(fopen(task ".inp", "r")){
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    int N, K;
    int H[200005][2], L[200005];
    cin >> N >> K;
    for(int i = 0; i < N - 1; i++){
       cin >> H[i][0] >> H[i][1] >> L[i];
    }
    cout << best_path(N, K, H, L);
}

Compilation message (stderr)

race.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main(){
      | ^~~~
race.cpp: In function 'int main()':
race.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccywFCjE.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccwho1ML.o:race.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccywFCjE.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