Submission #1147254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147254		AlgorithmWarrior	Race (IOI11_race)	C++20	100 / 100	379 ms	33336 KiB

race

#include <bits/stdc++.h>

using namespace std;

int const INF=1e9;
int const MAX=2e5+5;
int const MAXK=1e6+5;

int subsize[MAX];
int min_len[MAXK];

int get_subsize(int nod,int tata,vector<vector<pair<int,int>>>&tree,vector<bool>&dead){
    subsize[nod]=1;
    for(auto [u,w] : tree[nod])
        if(u!=tata && !dead[u])
            subsize[nod]+=get_subsize(u,nod,tree,dead);
    return subsize[nod];
}

int find_centroid(int nod,int tata,int total_size,vector<vector<pair<int,int>>>&tree,vector<bool>&dead){
    for(auto [u,w] : tree[nod])
        if(u!=tata && !dead[u] && subsize[u]>total_size/2)
            return find_centroid(u,nod,total_size,tree,dead);
    return nod;
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

void insert_values(int nod,int tata,int dist,int len,int K,bool type,vector<vector<pair<int,int>>>&tree,vector<bool>&dead){
    if(type)
        minself(min_len[dist],len);
    else
        min_len[dist]=INF;
    for(auto [u,w] : tree[nod])
        if(u!=tata && !dead[u] && dist+w<=K)
            insert_values(u,nod,dist+w,len+1,K,type,tree,dead);
}

void query_values(int nod,int tata,int dist,int len,int K,int& ans,vector<vector<pair<int,int>>>&tree,vector<bool>&dead){
    minself(ans,len+min_len[K-dist]);
    for(auto [u,w] : tree[nod])
        if(u!=tata && !dead[u] && dist+w<=K)
            query_values(u,nod,dist+w,len+1,K,ans,tree,dead);
}

void decompose(int nod,int K,int& ans,vector<vector<pair<int,int>>>&tree,vector<bool>&dead){
    get_subsize(nod,-1,tree,dead);
    int centroid=find_centroid(nod,-1,subsize[nod],tree,dead);
    for(auto [u,w] : tree[centroid])
        if(!dead[u] && w<=K){
            query_values(u,centroid,w,1,K,ans,tree,dead);
            insert_values(u,centroid,w,1,K,1,tree,dead);
        }
    for(auto [u,w] : tree[centroid])
        if(!dead[u])
            insert_values(u,centroid,w,1,K,0,tree,dead);
    min_len[0]=0;
    dead[centroid]=1;
    for(auto [u,w] : tree[centroid])
        if(!dead[u])
            decompose(u,K,ans,tree,dead);
}

int best_path(int N,int K,int H[][2],int L[]){
    vector<vector<pair<int,int>>>tree;
    tree.resize(N+5);
    int i;
    for(i=0;i<N-1;++i){
        auto [u,v]=H[i];
        auto w=L[i];
        tree[u].push_back({v,w});
        tree[v].push_back({u,w});
    }
    min_len[0]=0;
    for(i=1;i<K+5;++i)
        min_len[i]=INF;
    vector<bool>dead(N+5,0);
    int ans=INF;
    decompose(0,K,ans,tree,dead);
    if(ans<INF)
        return ans;
    return -1;
}

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