Submission #1221662

#TimeUsernameProblemLanguageResultExecution timeMemory
1221662Theo830Tree (IOI24_tree)C++20
0 / 100
2096 ms16544 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e9+7; const ll MOD = 998244353; typedef pair<ll,ll> ii; #define iii pair<ll,ii> #define id pair<ll,vector<ll> > #define f(i,a,b) for(ll i = a;i < b;i++) #define pb push_back #define vll vector<ll> #define F first #define S second #define all(x) (x).begin(), (x).end() ///I hope I will get uprating and don't make mistakes ///I will never stop programming ///sqrt(-1) Love C++ ///Please don't hack me ///@TheofanisOrfanou Theo830 ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst) ///Stay Calm ///Look for special cases ///Beware of overflow and array bounds ///Think the problem backwards ///Training #include "tree.h" int n; ll leaf = 0,l,r; std::vector<int> p, w; vector<vector<int> >adj; priority_queue<ii>pq[60005]; ll par[60005]; ll posa[60005]; ll find_par(ll a){ if(par[a] == a){ return a; } return par[a] = find_par(par[a]); } void enose(ll a,ll b){ ll p1 = find_par(a); ll p2 = find_par(b); if(p1 == p2){ return; } if(pq[p2].size() < pq[p1].size()){ swap(p1,p2); } while(!pq[p1].empty()){ pq[p2].push(pq[p1].top()); pq[p1].pop(); } par[p1] = p2; } ii solve(ll idx){ if(adj[idx].empty()){ return {l,l}; } ii ans = {0,0}; ll sum = 0; for(auto x:adj[idx]){ ii res = solve(x); enose(idx,x); ans.S += res.S; sum += res.F; } ll p = find_par(idx); while(sum > r && !pq[p].empty() && -pq[p].top().F < w[idx]){ ll thelo = min(pq[p].top().S,sum - r); ll we = -pq[p].top().F; ans.S += thelo * we; sum -= thelo; ll posa = pq[p].top().S - thelo; pq[p].pop(); if(posa){ pq[p].push(ii(-we,posa)); } } if(sum > r){ ans.S += w[idx] * (sum - r); sum = r; } if(sum > l){ pq[p].push(ii(-w[idx],sum - l)); priority_queue<ii>w; ll e = 0; while(e < sum - l){ ii f = pq[p].top(); ll thelo = min(sum - l - e,f.S); w.push(ii(f.F,thelo)); e += thelo; pq[p].pop(); } pq[p] = w; } ans.F = sum; return ans; } void init(std::vector<int> P, std::vector<int> W) { p = P; w = W; n = (int)p.size(); adj.assign(n+5,vector<int>()); f(i,1,n){ adj[p[i]].pb(i); } f(i,0,n){ if(adj[i].size() == 0){ leaf++; } } } long long query(int L, int R){ l = L; r = R; f(i,0,n){ while(!pq[i].empty()){ pq[i].pop(); } par[i] = i; posa[i] = INF; } return solve(0).S; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...