제출 #1225542

#제출 시각아이디문제언어결과실행 시간메모리
1225542Trumling트리 (IOI24_tree)C++20
10 / 100
2099 ms458140 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(v[x].top().S>L) v[start].push(v[x].top()); v[x].pop(); } } if(f[start]==0) { f[start]=L; ans+=w[start]*L; } while(f[start]>R && !v[start].empty() && -v[start].top().F < w[start]) { pair<ll,ll>curr=v[start].top(); v[start].pop(); ll can=curr.S; ll must=f[start]-R; if(can>must) { curr.S-=must; f[start]-=must; ans+=must*(-curr.F); v[start].push(curr); } else { curr.S-=can; f[start]-=can; ans+=can*(-curr.F); } } if(f[start]>R) { ans+=(f[start]-R)*w[start]; f[start]=R; } v[start].push({-w[start],f[start] - L}); ll used=0; priority_queue<pair<ll,ll>>pq; while(!v[start].empty() && used < (f[start] - L)) { pair<ll,ll>curr=v[start].top(); v[start].pop(); ll can = min(f[start] - L - used , curr.S); curr.S = can; pq.push(curr); 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...