제출 #964940

#제출 시각아이디문제언어결과실행 시간메모리
964940Younis_Dwai경주 (Race) (IOI11_race)C++14
21 / 100
3017 ms43860 KiB
#include "race.h" #include <bits/stdc++.h> #define F first #define S second #define pb push_back using namespace std ; const int MN=1e6+1; bitset<MN> vis; int res,k; vector<int> dp(MN),sz(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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...