Submission #1287929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287929		islam_2010	Race (IOI11_race)	C++20	100 / 100	494 ms	46148 KiB

race

// #include "race.h"
#include <bits/stdc++.h>
using namespace std;

const int sz = 2e5+5;
const int inf = 1e9 + 7;
vector<pair<int, int>> g[sz];
vector<int> sub(sz);
vector<bool> isremoved(sz);
int mn;
int subtree_size(int node, int p = -1){
    sub[node] = 1;
    for(auto i: g[node]){
        if(isremoved[i.first] || i.first == p) continue;
        sub[node] += subtree_size(i.first, node);
    }return sub[node];
}

int get_centroid(int node, int stsz, int p = -1){

    for(auto i: g[node]){
        if(isremoved[i.first] || i.first == p) continue;
        if(sub[i.first] * 2 > stsz){
            return get_centroid(i.first, stsz, node);
        }
    }return node;
}

void search(int node, int p, int d, int dist, int k, vector<pair<int,int>>& vals) {
    if (d > k) return;  
    vals.push_back({d, dist});
    for (auto i : g[node]) {
        if (isremoved[i.first] || i.first == p) continue;
        search(i.first, node, d + i.second, dist + 1, k, vals);
    }
}


void build(int node, int k){
    int stsz = subtree_size(node);
    int cent = get_centroid(node, stsz);
    isremoved[cent] = true;
    unordered_map<int,int> mp;
    mp[0] = 0;
    for(auto i: g[cent]){
        if(isremoved[i.first]) continue;

        vector<pair<int,int>> vals;
        vals.reserve(sub[i.first]);
        search(i.first, cent, i.second, 1 , k, vals);

        for(auto [d, dist]: vals){
            
            if(mp.count(k-d)){
                mn = min(mn, mp[k-d]+dist);
            }
        }
        for(auto [d, dist]: vals){
            if(!mp.count(d)){
                mp[d] = dist;
            }else {
                mp[d] = min(mp[d], dist);
            }
        }

    }
    
    
    for(auto i: g[cent]){
        if(!isremoved[i.first]){
            build(i.first, k);
        }
    }


}

int best_path(int N, int K, int H[][2], int L[]){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    

    for(int i = 0; i < N-1; i++){
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }mn = inf;
    build(0, K);
    return (mn == inf ? -1 : mn);
}

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