Submission #1227482

#TimeUsernameProblemLanguageResultExecution timeMemory
1227482PVM_pvmTree (IOI24_tree)C++20
10 / 100
2096 ms26016 KiB
#include "tree.h" #include<bits/stdc++.h> using namespace std; #define MAXN 200'007 int n; vector<int> p, w; vector<int> v[MAXN]; void init(std::vector<int> P, std::vector<int> W) { p = P; w = W; n = (int)p.size(); for (int q=1;q<n;q++) { v[ p[q] ].push_back(q); } } long long c[MAXN]; long long suma[MAXN]; void dfs(int x, int L, int R) { if (v[x].size()==0) { suma[x]=L; c[x]=L; //cout<<x<<" "<<suma[x]<<"\n"; return; } suma[x]=0; for (int q=0;q<v[x].size();q++) { //cout<<"dete mi e "<<v[x][q]<<"\n"; dfs(v[x][q],L,R); suma[x]+=suma[ v[x][q] ]; } //cout<<x<<" "<<suma[x]<<"\n"; if (suma[x]>R) { c[x]=R-suma[x]; suma[x]=R; } else { c[x]=0; } } long long query(int L, int R) { dfs(0,L,R); long long ans=0; for (int q=0;q<n;q++) { if (c[q]<0) ans+=w[q]*c[q]*-1; else ans+=w[q]*c[q]; } 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...