This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define pp pair<ll,int>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
using namespace std;
const int mxn=1e5+5;
vector<int>g[mxn];
int d[mxn]{0},w[mxn]{0};
map<int,ll>mp[mxn];
void dfs(int u){
for(auto v:g[u]){
dfs(v);
if(mp[u].size()>mp[v].size())swap(mp[u],mp[v]);
for(auto it : mp[v])mp[u][it.f]+=it.s;
}if(d[u]==0)return;
mp[u][d[u]]+=w[u];int cur=w[u];
auto it = mp[u].upper_bound(d[u]);
for(;it!=mp[u].end();){
if(it->s<=cur){auto ij=it;it++;cur-=ij->s;mp[u].erase(ij);}
else {it->s-=cur;break;}
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,m,k;cin>>n>>m>>k;
for(int i=2;i<=n;i++){
int p;cin>>p;g[p].pb(i);
}
for(int i=1;i<=m;i++){
int v;cin>>v;cin>>d[v]>>w[v];
}dfs(1);ll rs=0;
for(auto it : mp[1])rs+=it.s;
cout<<rs;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |