Submission #1130455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130455		akzytr	Race (IOI11_race)	C++17	0 / 100	4 ms	5940 KiB

race

#include <bits/stdc++.h>
#define ve vector
#define ar array 
#define pb push_back
#define ins insert

#define endl '\n'
#define ll long long
using namespace std;

const int MXN = 2e5+5;
ve<pair<int, ll>> adj[MXN];
ve<bool> proc(MXN, false);
ve<int> sz(MXN, 0);
int K;

void szdfs(int x, int p){
    sz[x] = 1;
    for(auto [i, _] : adj[x]){
        if(i != p && !proc[i]){
            sz[x] += sz[i];
        }
    }
}

int find_centroid(int x, int n, int p){
    for(auto [i, _] : adj[x]){
        if(!proc[i] && i != p && sz[i] > n/2){
            return find_centroid(i, n, x);
        }
    }
    return x;
}

map<int, int> bk;
int ans = 1e9;
void upddfs(int x, int p, int cur, int down){
    if(bk.count(cur)){
        bk[cur] = min(bk[cur], down);
    }
    else{
        bk[cur] = down;
    }

    for(auto [i, c] : adj[x]){
        if(i != p && !proc[i] && cur + c <= K){
            upddfs(i, x, cur + c, down+1);
        }
    }
}

void chkdfs(int x, int p, int cur, int down){
    if(bk.count(K-cur)){
        ans = min(ans, down + bk[K-cur]);
    }
    for(auto [i, c] : adj[x]){
        if(i != p && !proc[i] && cur + c <= K){
           chkdfs(i, x, cur + c, down+1);
        }
    }
}


int decompo(int x){
    szdfs(x, -1);
    int cent = find_centroid(x, sz[x], -1);
    for(auto [i, c] : adj[cent]){
        if(!proc[i]){
            upddfs(i, cent, c, 1);
            chkdfs(i, cent, c, 1);
        }
    }

    proc[cent] = 1;
    while(!bk.empty()){
        bk.erase(bk.begin());
    }
    for(auto [i, _] : adj[cent]){
        if(proc[i]){continue;}
        decompo(i);
    }
}
int best_path(int N, int k, int H[][2], int L[]){
    K = k;
    for(int i = 0; i < N-1; i++){
        adj[H[i][0]].pb({H[i][1], L[i]});
        adj[H[i][1]].pb({H[i][0], L[i]});
    }
    szdfs(0, -1);
    decompo(0);
    if(ans == 1e9){
        ans = -1;
    }   
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'int decompo(int)':
race.cpp:82:1: warning: no return statement in function returning non-void [-Wreturn-type]
   82 | }
      | ^

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57