Submission #764273

#	Time	Username	Problem	Language	Result	Execution time	Memory
764273		Ryuga_	Race (IOI11_race)	C++14	0 / 100	10 ms	8916 KiB

race

 
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define F first
#define S second 
typedef long long ll;
 
vector<pair<int,int>>g[N];
int sub[N] , process[N];
ll n , k ;
int mp[1000100];
int dfs(int u , int p)
{
        sub[u] = 1;
        for(auto v : g[u]){
                if(v.F != p && !process[v.F]){
                        sub[u] += dfs(v.F,u);
                }
        }
 
        return sub[u];
}
int centroid(int u , int p , int req)
{
        for(auto v : g[u]){
                if(v.F != p && !process[v.F] && sub[v.F] >= req){
                        return centroid(v.F,u,req);
                }
        }
 
        return u;
}
 
int ans = INT_MAX;
void f(int u ,int p , int keep , ll depth , int level)
{
        if(depth > k) return;
        
        
        if(!keep){
                ll x = k-depth;
                if(mp[x] != -1){
                        ans = min(ans,mp[x] + level);
                }
                 
        }
        else{
                if(mp[depth] == -1){
                        mp[depth] = level;
                }

                else mp[depth] = min(mp[depth],level);
        }
 
        for(auto v : g[u]){
                if(v.F != p && !process[v.F]){
                        f(v.F,u,keep,depth+v.S,level+1);
                }
        }
        
}
 
void decompose(int u)
{
        ll x = dfs(u,-1);
        ll cen = centroid(u,0,x/2);
        process[cen] = 1;
        mp[0] = 0;
        for(auto v : g[cen]){
                if(!process[v.F]){
                        f(v.F,cen,0,v.S,1);
                        f(v.F,cen,1,v.S,1);
                }
        }
       
        memset(mp,-1,sizeof(mp));
        
        for(auto v : g[cen]){
                if(!process[v.F]) decompose(v.F);
        }
 
}

int best_path(int _N, int _K, int H[][2], int L[])
{
        memset(mp,-1,sizeof(mp));
        for(int i = 0 ; i < _N - 1 ; i ++){
                int x = H[i][0] , y = H[i][1] , w = L[i];
                g[x].push_back({y,w});
                g[y].push_back({x,w});
        }
        decompose(0);
        if(ans == INT_MAX) ans = -1;
        return ans;
        
}

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