제출 #499784

#제출 시각아이디문제언어결과실행 시간메모리
499784HappyPacMan경주 (Race) (IOI11_race)C++14
9 / 100
114 ms32256 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 15; vector<pair<int,int> > adj[MAXN]; map<int,int> cost[MAXN]; int res = MAXN; void dfs(int u,int p,long long k,long long d,int l){ cost[u][d] = l; for(auto v : adj[u]){ if(v.first == p) continue; dfs(v.first,u,k,d+v.second,l+1); if(cost[u].size() < cost[v.first].size()) swap(cost[u],cost[v.first]); for(auto w : cost[v.first]){ int split = k - w.first + 2*d; if(cost[v.first].count(split)) res = min(res,w.second+cost[v.first][split]-2*l); if(cost[u].count(w.first)) cost[u][w.first] = min(cost[u][w.first],w.second); else cost[u][w.first] = w.second; } } if(cost[u].count(d+k)) res = min(res,cost[u][d+k]-l); } int best_path(int N, int K, int H[][2], int L[]){ for(int i=0;i<N-1;i++){ adj[H[i][0]].emplace_back(H[i][1],L[i]); adj[H[i][1]].emplace_back(H[i][0],L[i]); } dfs(0,0,K,0,0); if(res == MAXN) res = -1; return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...