Submission #713011

#	Time	Username	Problem	Language	Result	Execution time	Memory
713011		Ahmed57	Race (IOI11_race)	C++14	100 / 100	1392 ms	51184 KiB

race

#include <bits/stdc++.h>

using namespace std;
int sz[200007];long long all = 0;
int vis[200007];
vector<pair<int,int>> adj[200007];
bool ss = 0;
map<long long,long long> mp;
long long k;
long long ans = 1e18;
void calc(int no,int pr,long long dep,long long cost){
    if(cost>k)return ;
    if(ss){
        if(mp[cost]==0)mp[cost] = dep;
        else mp[cost] = min(mp[cost],dep);
    }else{
        if(mp[k-cost]!=0){
            ans = min(ans,dep+mp[k-cost]-2);
        }
    }
    for(auto i:adj[no]){
        if(i.first==pr||vis[i.first])continue;
        calc(i.first,no,dep+1,cost+i.second);
    }
}
int dfs(int no,int pr){
    sz[no] = 1;
    for(auto i:adj[no]){
        if(i.first==pr||vis[i.first]!=0)continue;
        sz[no]+=dfs(i.first,no);
    }
    return sz[no];
}
int get_centroid(int no,int ss,int pr){
    for(auto i:adj[no]){
        if(pr==i.first||vis[i.first]!=0)continue;
        if(sz[i.first]*2>ss){
            return get_centroid(i.first,ss,no);
        }
    }
    return no;
}
void centroid(int no){
    int cen = get_centroid(no,dfs(no,-1),-1);
    mp.clear();
    mp[0] = 1;
    vis[cen] = 1;
    for(auto i:adj[cen]){
        if(vis[i.first])continue;
        ss = 0;
        calc(i.first,-1,2,i.second);
        ss = 1;
        calc(i.first,-1,2,i.second);
    }
    for(auto i:adj[cen]){
        if(vis[i.first])continue;
        centroid(i.first);
    }
}
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]+1].push_back({H[i][1]+1,L[i]});
        adj[H[i][1]+1].push_back({H[i][0]+1,L[i]});
    }
    centroid(1);
    return (ans==1e18?-1:ans);
}
/*
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int N = 3 , K = 3;
    int L[] = {1,2,4};
    int H[3][2] = {{0,1},{1,2},{1,3}};
    cout<<best_path(N,K,H,L);
}
*/

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