Submission #964942

#	Time	Username	Problem	Language	Result	Execution time	Memory
964942		Younis_Dwai	Race (IOI11_race)	C++14	21 / 100	3022 ms	41248 KiB

race

#include "race.h"
#include <vector>
#define F first
#define S second
#define pb push_back
using namespace std ;
const int MN=1e6+1;
int res,k;
vector<int> dp(MN),sz(MN);
vector<bool> vis(MN);
vector<pair<int,int>> adj[MN];
void dfs_sz(int node , int par){
     sz[node]=1;
     for(auto u : adj[node]){
         if(vis[u.F] || u.F==par) continue ;
         dfs_sz(u.F,node);
     }
     return ;
}
int  get_centroid(int node ,int par , int d){
     for(auto u : adj[node]){
         if(vis[u.F] || u.F==par || sz[u.F]<=d) continue ;
         return get_centroid(u.F,node,d);
     }
     return node;
}
void dfs_calc(int node, int par , int done ,int dis){
     res=min(res,dp[k-dis]+done);
     for(auto u : adj[node]){
         if(u.F==par || vis[u.F] || dis+u.S>k) continue ;
         dfs_calc(u.F,node,done+1,dis+u.S);
     }
     return ;
}
void dfs_upd(int node , int par , int done , int dis){
     dp[dis]=min(done,dp[dis]);
     for(auto u : adj[node]){
         if(u.F==par || vis[u.F] || dis+u.S>k) continue ;
         dfs_upd(u.F,node,done+1,dis+u.S);
     }
     return ;
}
void dfs_fill(int node , int par ,int dis){
     if(dp[dis]!=1e9) dp[dis]=1e9;
     for(auto u : adj[node]){
         if(u.F==par || vis[u.F] || dis+u.S>k) continue ;
         dfs_fill(u.F,node,dis+u.S);
     }
     return ;
}
void dfs(int node){
     dfs_sz(node,node);
     int centroid=get_centroid(node,node,800);
     vis[centroid]=1;
     dp[0]=0;
     for(auto u : adj[centroid]){
         if(vis[u.F] || u.S>k) continue ;
         dfs_calc(u.F,centroid,1,u.S);
         dfs_upd(u.F,centroid,1,u.S);
     }
     for(auto u : adj[centroid]){
         if(u.S>k || vis[u.F]) continue ;
         dfs_fill(u.F,centroid,u.S);
     }
     for(auto u :  adj[centroid]){
         if(vis[u.F]) continue ;
         dfs(u.F);
     }
     return ;
}
int best_path(int N, int K, int H[][2], int L[]){
    res=1e9;
    k=K;
    for(int i=0;i<=K;i++) dp[i]=1e9;
    for(int i=0;i<N-1;i++){
        adj[H[i][0]].pb({H[i][1],L[i]});
        adj[H[i][1]].pb({H[i][0],L[i]});
    }
    dfs(0);
    if(res==1e9) return -1;
    else return res;
    return 0;
}

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