Submission #1113059

#TimeUsernameProblemLanguageResultExecution timeMemory
1113059MatkapRace (IOI11_race)C++17
100 / 100
286 ms38648 KiB
/* Author:Matkap(prefix_sum) */ #include "race.h" #include <bits/stdc++.h> #include <array> using namespace std; #define endl "\n" #define ar array #define all(x) x.begin(),x.end() const int INF = 1e9 + 7 , MOD = 1e9 + 7; const int mxN = 2e5 + 7, mxK = 2e6 + 7; vector<ar<int,2>> adj[mxN]; int rem[mxN]; int sub[mxN]; int cnt[mxK]; int ans = INF; int k1; vector<int> vec; int find_subtree_size(int pos,int par = -1) { sub[pos] = 1; for(auto [it, dist] : adj[pos]) { if(it == par || rem[it]) continue; sub[pos] += find_subtree_size(it, pos); } return sub[pos]; } int find_centroid(int sub_size, int pos,int par = -1) { for(auto [it, dist] : adj[pos]) { if(it == par || rem[it]) continue; if(sub[it] > sub_size / 2) return find_centroid(sub_size, it, pos); } return pos; } void solve(int pos,int par,int cur_path,int mode, int depth = 1) { if(cur_path > k1) return; if(mode == 1) cnt[cur_path] = min(cnt[cur_path], depth), vec.push_back(cur_path); else ans = min(ans, cnt[k1 - cur_path] + depth); for(auto [it, dist] : adj[pos]) { if(rem[it] || it == par) continue; solve(it,pos,cur_path + dist,mode,depth + 1); } } void build_decomp(int pos) { int centroid = find_centroid(find_subtree_size(pos), pos); //cout << centroid << endl; rem[centroid] = 1; vec.clear(); for(auto [it, dist] : adj[centroid]) { if(!rem[it]) { solve(it,-1,dist,0); solve(it,-1,dist,1); } } for(auto it : vec) cnt[it] = INF; cnt[0] = 0; for(auto [it, dist] : adj[centroid]) { if(rem[it]) continue; build_decomp(it); } } int best_path(int n,int k, int h[][2], int l[]) { k1 = k; fill(cnt, cnt + mxK, INF); cnt[0] = 0; for(int i = 0;n - 1 > i;i++) { adj[h[i][0]].push_back({h[i][1], l[i]}); adj[h[i][1]].push_back({h[i][0], l[i]}); } build_decomp(0); if(ans == INF) return -1; return ans; } /*int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int h[1000][2]; int l[1000]; int n; int k; cin >> n >> k; for(int i = 0;n - 1 > i;i++) for(int j = 0;2 > j;j++) cin >> h[i][j]; for(int i = 0;n - 1 > i;i++) cin >> l[i]; cout << best_path(n, k, h, l) << endl; }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...