Submission #1264359

#TimeUsernameProblemLanguageResultExecution timeMemory
1264359BlockOG경주 (Race) (IOI11_race)C++20
21 / 100
3096 ms32068 KiB
#include <bits/stdc++.h> // mrrrow meeow :3 // go play vivid/stasis now! it's free on steam #define fo(i, a, b) for (auto i = (a); i < (b); i++) #define of(i, a, b) for (auto i = (b); i-- > (a);) #define f first #define s second #define pb push_back #define pob pop_back #define lb lower_bound #define ub upper_bound #define be(a) a.begin(), a.end() using namespace std; int ____init = [] { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); return 0; }(); vector<pair<int, int>> adj[200000]; int nd[200000]; long long nl[200000]; int k; pair<unordered_map<long long, int>, int> dfs(int i, int p = -1, int d = 0, long long l = 0) { nd[i] = d, nl[i] = l; unordered_map<long long, int> m = {{l, d}}; int md = 1000000; for (auto [j, jl] : adj[i]) { if (j == p) continue; auto [rm, rmd] = dfs(j, i, d + 1, l + jl); md = min(md, rmd); // for (auto it = rm.ub(l + k); it != rm.end(); rm.erase(it++)); if (rm.size() > m.size()) swap(rm, m); for (auto [cl, cd] : rm) { if (m.count(l + k - (cl - l))) md = min(md, cd - d + m[l + k - (cl - l)] - d); } for (auto [cl, cd] : rm) { if (m.count(cl)) m[cl] = min(m[cl], cd); else m[cl] = cd; } } return {m, md}; } int best_path(int n, int K, int h[][2], int l[]) { k = K; fo(i, 0, n - 1) { adj[h[i][0]].pb({h[i][1], l[i]}); adj[h[i][1]].pb({h[i][0], l[i]}); } int res = dfs(0).s; return res == 1000000 ? -1 : 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...