Submission #1130459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130459		akzytr	Race (IOI11_race)	C++17	100 / 100	844 ms	49772 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;

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

    return sz[x];
}

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;
}

int ans = 1e9;
void upddfs(int x, int p, int cur, int down, map<int,int> &bk){
    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, bk);
        }
    }
}

void chkdfs(int x, int p, int cur, int down, map<int, int> &bk){
    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, bk);
        }
    }
}


void decompo(int x){
    map<int, int> bk;
    bk[0] = 0;

    int cent = find_centroid(x, szdfs(x, -1), -1);

    for(auto [i, c] : adj[cent]){
        if(!proc[i]){
            chkdfs(i, cent, c, 1, bk);
            upddfs(i, cent, c, 1, bk);
        }
    }

    proc[cent] = 1;
    for(auto [i, _] : adj[cent]){
        if(!proc[i]){
            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;
}

// int main(){
//     int N, k;
//     cin >> N >> k;

//     int H[N-1][2];
//     int L[N-1];
//     for(int i = 0; i < N-1; i++){
//         cin >> H[i][0] >> H[i][1] >> L[i];
//     }
//     cout << best_path(N, k, H, L)<<endl;
// }

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