Submission #1236406

#TimeUsernameProblemLanguageResultExecution timeMemory
1236406MalixTree (IOI24_tree)C++20
23 / 100
2095 ms11876 KiB
#include "tree.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<int,int,int> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) #define all(x) (x).begin(),(x).end() ll INF=1000000000000000010; int inf=1e9+10; ll M=1e9+7; int n; std::vector<int> p, w; void init(std::vector<int> P, std::vector<int> W) { p=P;w=W;n=P.size(); } long long query(int L, int R) { ll l=L,r=R; vector<ll> a(n,0),b(n,0); for(int i=n-1;i>=0;i--){ if(a[i]==0)b[i]=l; else if(a[i]>l)b[i]=l-a[i]; a[i]+=b[i]; if(i!=0)a[p[i]]+=a[i]; } priority_queue<pi> pq; REP(i,0,n)pq.push({w[i],i}); vi vis(n,0); while(!pq.empty()){ int x=pq.top().S; pq.pop(); vis[x]=1; if(b[x]>=0)continue; ll y=min(r-l,abs(b[x])); int z=x,ps=-1; vi arr; while(p[z]!=-1){ z=p[z]; if(vis[z]){ y=min(y,r-a[z]); arr.PB(z); } else{ ps=z; break; } } b[x]+=y;a[x]+=y; if(ps!=-1)b[ps]-=y; for(auto u:arr)a[u]+=y; } ll ans=0; REP(i,0,n)ans+=(ll)w[i]*abs(b[i]); 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...