Submission #389019

#TimeUsernameProblemLanguageResultExecution timeMemory
389019mosiashvililukaFireworks (APIO16_fireworks)C++14
0 / 100
1 ms460 KiB
#include<bits/stdc++.h> using namespace std; long long a,b,c,d,e,i,j,ii,jj,zx,xc,Pi,dp[5009]; const long long N=1000000000000000000LL; vector <pair <long long, long long> > v[5009]; pair <long long, long long> p[5009],P[5009]; void dfs(long long q, long long w){ if(q>a){ p[q].first=p[q].second=0; return; } for(vector <pair <long long, long long> >::iterator it=v[q].begin(); it!=v[q].end(); it++){ if((*it).first==w) continue; dfs((*it).first,q); dp[q]+=dp[(*it).first]; } Pi=0; for(vector <pair <long long, long long> >::iterator it=v[q].begin(); it!=v[q].end(); it++){ if((*it).first==w) continue; Pi++; P[Pi].first=p[(*it).first].first+(*it).second; P[Pi].second=p[(*it).first].second+(*it).second; } e=N; for(j=0; j<=300; j++){ zx=0; for(i=1; i<=Pi; i++){ if(j>P[i].second){ zx+=j-P[i].second; } if(j<P[i].first){ zx+=P[i].first-j; } } if(e>zx) e=zx; } p[q].first=302;p[q].second=-1; dp[q]+=e; for(j=0; j<=300; j++){ zx=0; for(i=1; i<=Pi; i++){ if(j>P[i].second){ zx+=j-P[i].second; } if(j<P[i].first){ zx+=P[i].first-j; } } if(e==zx){ p[q].first=min(p[q].first,j); p[q].second=max(p[q].second,j); } } //cout<<q<<" "<<dp[q]<<" "<<p[q].first<<" "<<p[q].second<<endl; } int main(){ ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>a>>b; for(i=2; i<=a; i++){ cin>>c>>d; v[c].push_back(make_pair(i,d)); } for(i=a+1; i<=a+b; i++){ cin>>c>>d; v[c].push_back(make_pair(i,d)); } dfs(1,0); cout<<dp[1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...