Submission #1225530

#TimeUsernameProblemLanguageResultExecution timeMemory
1225530TrumlingTree (IOI24_tree)C++20
0 / 100
2100 ms214680 KiB
//Trumling © //Αφόδευε υψηλά και ηγνάντει #include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define F first #define S second #define enter cout<<'\n'; #define INF 99999999999999 #define MOD 1000000007 #define all(x) x.begin(),x.end() #include "tree.h" int n; vector<ll> w; vector<ll>f; vector<vector<ll>>g; vector<priority_queue<pair<ll,ll>>>v; ll ans=0; void dfs(int start,int pre,int L,int R) { for(auto x:g[start]) if(x!=pre) { dfs(x,start,L,R); f[start]+=f[x]; while(!v[x].empty()) { if(f[v[x].top().S]>L) v[start].push(v[x].top()); v[x].pop(); } } v[start].push({-w[start],start}); if(f[start]==0) { f[start]=L; ans+=w[start]*L; } while(f[start]>R) { ll can=f[v[start].top().S]-L; ll must=f[start]-R; if(can>must) { if(v[start].top().S!=start) f[v[start].top().S]-=must; f[start]-=must; ans+=must*(-v[start].top().F); } else { if(v[start].top().S!=start) f[v[start].top().S]-=can; f[start]-=can; ans+=can*(-v[start].top().F); v[start].pop(); } } ll used=0,sum=f[start]; priority_queue<pair<ll,ll>>pq; while(!v[start].empty() && used < sum - L) { ll can = min(sum - L - used , f[v[start].top().S] - L); f[v[start].top().S]= L + can; pq.push(v[start].top()); v[start].pop(); used+=can; } v[start]=pq; } void init(std::vector<int> p, std::vector<int> W) { for(auto x:W) w.pb(x); n = (int)p.size(); g.assign(n,vector<ll>()); for(int i=1;i<n;i++) { // cout<<i<<' '<<p[i]<<','; g[i].pb(p[i]); g[p[i]].pb(i); } } long long query(int L, int R) { ans=0; f.assign(n,0); v.assign(n,priority_queue<pair<ll,ll>>()); dfs(0,0,L,R); 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...