Submission #1192481

#TimeUsernameProblemLanguageResultExecution timeMemory
1192481farica경주 (Race) (IOI11_race)C++20
100 / 100
321 ms102604 KiB
#include<bits/stdc++.h> #include "race.h" using namespace std; using vi = vector<int>; using pi = pair<long long,long long>; typedef long long ll; ll ans, k; vector<ll> depth; vector<map<ll,int>>paths; vector<vector<pi>>adjL; void dfs(int pos, int prev, ll sum) { paths[pos][sum] = depth[pos]; ll target = k + 2*sum; for(pi adj: adjL[pos]) { if(adj.first == prev) continue; depth[adj.first] = depth[pos] + 1; dfs(adj.first, pos, sum + adj.second); if(paths[adj.first].size() > paths[pos].size()) swap(paths[adj.first], paths[pos]); for(auto it: paths[adj.first]) { if(paths[pos].find(target - it.first) != paths[pos].end()) { ll cur = paths[pos][target-(it.first)] + (it.second) - 2 * depth[pos]; if(ans == -1) ans = cur; else ans = min(ans, cur); } } for(auto it: paths[adj.first]) { if(paths[pos].find(it.first) == paths[pos].end()) paths[pos].insert(it); else paths[pos][it.first] = min(paths[pos][it.first], it.second); } } } int best_path(int N, int K, int H[][2], int L[]) { ans = -1; k = K; paths.resize(N); depth.assign(N, 0); adjL.assign(N, vector<pi>()); for(int i=0; i<N-1; ++i) { adjL[H[i][0]].push_back({H[i][1], L[i]}); adjL[H[i][1]].push_back({H[i][0], L[i]}); } depth[0] = 1; dfs(0,0,0); 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...