Submission #1192557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192557		aren_dance	Race (IOI11_race)	C++20	100 / 100	635 ms	40172 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int l=2e5+1;
vector<pair<int,int>> adj[l];
int n,k;
int ans;
bool used[l];
int cnt[l];
int num;
vector<int> p;
int mn(int x,int y){
    if(x==-1){
        return y;
    }
    return min(x,y);
}
void dfs(int node,int parent){
    ++num;
    cnt[node]=1;
    for(auto i:adj[node]){
        if(i.first==parent){
            continue;
        }
        if(used[i.first]){
            continue;
        }
        dfs(i.first,node);
        cnt[node]+=cnt[i.first];
    }
}
bool center(int node,int parent){
    for(auto i:adj[node]){
        if(used[i.first])
        continue;
        if(i.first==parent){
            continue;
        }
        if(cnt[i.first]>num/2){
            return 0;
        }
    }
    return 1;
}
int find_centroid(int node){
    num=0;
    dfs(node,-1);
    if(num==1){
        return -1;
    }
    int gag=node;
    int parent=-1;
    while(!center(gag,parent)){
        for(auto i:adj[gag]){
            if(used[i.first]){
                continue;
            }
            if(i.first==parent){
                continue;
            }
            if(cnt[i.first]>num/2){
                parent=gag;
                gag=i.first;
                break;
            }
        }
    }
    used[gag]=1;
    return gag;
}
map<int,int> mp;
vector<pair<int,int>> mas;
void dfsx(int node,int parent,int root,int her,int r){
    if(node!=root){
        mas.push_back({her,r});
        auto it=mp.find(k-her);
        if(it!=mp.end()){
            ans=mn(ans,it->second+r);
        }
    }
    for(auto i:adj[node]){
        if(i.first==parent){
            continue;
        }
        if(used[i.first]){
            continue;
        }
        if(node==root){
            dfsx(i.first,node,root,her+i.second,r+1);
            auto it=mp.find(k);
            if(it!=mp.end()){
                ans=mn(ans,it->second);
            }
            for(auto j:mas){
                auto itx=mp.find(j.first);
                if(itx==mp.end()){
                    mp.insert({j.first,j.second});
                }
                else{
                    itx->second=min(itx->second,j.second);
                }
            }
            mas.clear();
            continue;
        }
        dfsx(i.first,node,root,her+i.second,r+1);
    }
}
void solve_helper(int u){
    mp.clear();
    mp.insert({0,0});
    dfsx(u,-1,u,0,0);
}
void solve(int node){
    int u=find_centroid(node);
    if(u==-1){
        return ;
    }
    solve_helper(u);
    for(auto i:adj[u]){
        if(!used[i.first]){
            solve(i.first);
        }
    }
    //cout<<node<<" "<<u<<'\n';
}
int best_path(int N, int K, int H[][2], int L[]){
    n=N;
    k=K;
    ans=-1;
    for(int i=0;i<n-1;++i){
        adj[H[i][1]].push_back({H[i][0],L[i]});
        adj[H[i][0]].push_back({H[i][1],L[i]});
    }
    solve(0);
    return ans;
}

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