Submission #1211525

#TimeUsernameProblemLanguageResultExecution timeMemory
1211525Br3adRace (IOI11_race)C++20
0 / 100
3 ms6720 KiB
#include <iostream> #include <fstream> #include <iomanip> #include <algorithm> #include <functional> #include <numeric> #include <cstring> #include <string> #include <cmath> #include <vector> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define ll long long #define ull unsigned long long #define f first #define s second #define PF push_front #define PB push_back #define MP make_pair #define pi pair<int, int> #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define max(a, b) ((a > b)? a : b) #define min(a, b) ((a < b)? a : b) #define max3(a, b, c) max(max(a, b), c) #define min3(a, b, c) min(min(a, b), c) const int N = 2e5 + 5; const int M = 1e9 + 7; const int inf = 0x3f3f3f3f; const ll int INF = 1e18; int _n, _k; map<int, int> mp; vector<pi> adj[N]; vector<int> sz(N), val(N); vector<bool> processed(N, false); int get_subtree_size(int cur, int prev = -1){ sz[cur] = 1; for(auto [child, _] : adj[cur]){ if(processed[child] || child == prev) continue; sz[cur] += get_subtree_size(child, cur); } return sz[cur]; } int get_centroid(int thres, int cur, int prev = -1){ for(auto [child, _] : adj[cur]){ if(processed[child] || child == prev) continue; if(sz[child] >= thres) return get_centroid(thres, child, cur); } return cur; } int ans = N; void get_cnt(int cur, int prev, bool filling, int depth, int cnt = 1){ if(depth > _k) return; if(filling){ if(mp[depth] == 0) mp[depth] = cnt; else mp[depth] = min(mp[depth], cnt); }else { int tmp = mp[_k - depth]; if(mp[tmp]) ans = min(ans, cnt + mp[tmp]); } for(auto [child, w] : adj[cur]){ if(processed[child] || child == prev) continue; get_cnt(child, cur, filling, depth+w, cnt+1); } } void centroid_decomp(int node = 1){ int centroid = get_centroid(get_subtree_size(node) >> 1, node); processed[centroid] = true; mp.clear(); for(auto [child, w] : adj[centroid]){ if(processed[child]) continue; get_cnt(child, centroid, false, w); get_cnt(child, centroid, true, w); } for(auto [child, _] : adj[centroid]){ if(!processed[child]) centroid_decomp(child); } } int best_path(int n, int k, int H[][2], int L[]){ _n = n; _k = k; for(int i = 0; i < n-1; i++){ int a = H[i][0], b = H[i][1]; adj[a].PB({b, L[i]}); adj[b].PB({a, L[i]}); } centroid_decomp(); 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...