Submission #1005811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005811		Mardonbekhazratov	Race (IOI11_race)	C++17	100 / 100	971 ms	66716 KiB

race

#include<race.h>
#include<bits/stdc++.h>

using namespace std;

vector<int>subtree;
vector<bool>removed;
vector<vector<pair<int,int>>>v;

int get_size(int node,int parent = -1){
    subtree[node]=1;
    for(auto [x,w]:v[node]){
        if(!removed[x] && x!=parent){
            subtree[node]+=get_size(x,node);
        }
    }
    return subtree[node];
}

int get_centroid(int node, int n, int parent = -1){
    for(auto [x,w]:v[node]){
        if(!removed[x] && x!=parent && subtree[x]*2>n)
            return get_centroid(x,n,node);
    }
    return node;
}

int n,k;
int ans = 1e9;

void get_cnt(int node, map<int,int> &cnt, int dis, bool filling, int depth = 1, int parent = -1){
    if(dis>k) return;

    if(filling) cnt[dis]=dis == k ? depth : (cnt[dis]==0?depth:min(depth,cnt[dis]));
    else ans = min(ans,dis==k ? depth : (cnt[k-dis]==0?(int)1e9:cnt[k-dis])+depth);
    for(auto [x,w]:v[node]){
        if(x!=parent && !removed[x]){
            get_cnt(x,cnt,dis+w,filling,depth+1,node);
        }
    }
}

void build_centroid(int node = 0){
    int centroid = get_centroid(node,get_size(node));

    removed[centroid]=true;

    map<int,int>cnt;
    for(auto [x,w]:v[centroid]){
        if(!removed[x]){
            get_cnt(x,cnt,w,false);
            get_cnt(x,cnt,w,true);
        }
    }

    for(auto [x,w]:v[centroid]){
        if(!removed[x]){
            build_centroid(x);
        }
    }
}


int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    k=K;
    subtree.resize(n);
    v.resize(n);
    removed.assign(n,false);
    for(int i=0;i<n-1;i++){
        v[H[i][0]].push_back({H[i][1],L[i]});
        v[H[i][1]].push_back({H[i][0],L[i]});
    }
    build_centroid();

    return ans == (int)1e9 ? -1 : ans;
}

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