Submission #389019

#	Time	Username	Problem	Language	Result	Execution time	Memory
389019		mosiashvililuka	Fireworks (APIO16_fireworks)	C++14	0 / 100	1 ms	460 KiB

fireworks

#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;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45