제출 #738400

#제출 시각아이디문제언어결과실행 시간메모리
738400Baytoro경주 (Race) (IOI11_race)C++17
0 / 100
7 ms14432 KiB
#include "race.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define fr first #define sc second #define all(x) x.begin(),x.end() const ll NN=2e5+5; vector<pair<int,int>> g[NN]; ll ans=1e9,k; map<ll,ll> mp[NN]; void dfs(int x, int p, ll d, int depth){ mp[x][d]=depth; for(auto it: g[x]){ if(it.fr==p) continue; dfs(it.fr,x,d+it.sc,depth+1); if(mp[x].size()<mp[it.fr].size()) swap(mp[x],mp[it.fr]); for(auto i: mp[it.fr]){ ll target=k-i.fr+2*d; if(mp[x].find(target)!=mp[x].end()){ ans=min(ans,mp[x][target]+i.sc-2*depth); } } for(auto i: mp[it.fr]) mp[x].insert(i); } } int best_path(int N, int K, int H[][2], int L[]){ k=K; for(int i=0;i<N-1;i++){ int a=H[i][0],b=H[i][1],c=L[i]; g[a].pb({b,c}); g[b].pb({a,c}); } dfs(0,-1,0,0); if(ans>N) ans=-1; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...