제출 #866659

#제출 시각아이디문제언어결과실행 시간메모리
866659Irate경주 (Race) (IOI11_race)C++14
0 / 100
4 ms20552 KiB
#include<bits/stdc++.h> #include "race.h" using namespace std; const int mxN = 2e5 + 3; vector<pair<int, int>>G[mxN]; map<long long, int>cnt[mxN]; long long length[mxN]; int K; int mn = 1e9, depth[mxN]; void dfs(int node, int par){ cnt[node][length[node]] = depth[node]; for(pair<int, int>& v : G[node]){ if(v.first != par){ depth[v.first] = depth[node] + 1; length[v.first] = length[node] + v.second; dfs(v.first, node); if(cnt[node].size() < cnt[v.first].size())swap(cnt[node], cnt[v.first]); for(auto itr = cnt[v.first].begin();itr != cnt[v.first].end();++itr){ long long num = itr->first; int dep = itr->second; if(cnt[node].count(K + 2 * length[node] - num)){ mn = min(mn, dep + cnt[node][K + 2 * length[node] - num] - 2 * depth[node]); } if(cnt[node].count(num)){ cnt[node][num] = max(cnt[node][num], dep); } else{ cnt[node][num] = dep; } } } } } int best_path(int n, int k, int H[][2], int L[]){ K = k; for(int i = 0;i < n - 1;++i){ int u = H[i][0], v = H[i][1]; G[u].push_back({v, L[i]}); G[v].push_back({u, L[i]}); } dfs(0, 0); if(mn == 1e9)return -1; return mn; } // int main() // { // ios_base::sync_with_stdio(0); // cin.tie(0); // int n; // cin >> n >> K; // int H[n - 1][2], L[n - 1]; // for(int i = 0;i < n - 1;++i){ // cin >> H[i][0] >> H[i][1] >> L[i]; // } // cout << best_path(n, K, H, L); // } /* 11 12 0 1 3 0 2 4 2 3 5 3 4 4 4 5 6 0 6 3 6 7 2 6 8 5 8 9 6 8 10 7 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...