oj.uz

Submission #1092662

# Submission time Handle Problem Language Result Execution time Memory
1092662 2024-09-24T17:33:36 Z alexander707070 Fireworks (APIO16_fireworks) C++14
7 / 100
 9 ms 14600 KB 
#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;

const long long inf=1e17;

int n,m;
int p[MAXN],c[MAXN];
vector< pair<int,long long> > v[MAXN],g[MAXN];
vector<long long> dists;

long long sz[MAXN],ans,dist[MAXN];

void dfs(int x,long long d){
	sz[x]=(v[x].empty());
	dist[x]=d;

	if(sz[x]==1)dists.push_back(d);

	for(int i=0;i<v[x].size();i++){
		dfs(v[x][i].first,d+v[x][i].second);

		sz[x]+=sz[v[x][i].first];
	}
}

long long dp[MAXN];
long long sum;

void solve(int x,long long len,long long e){
	if(v[x].empty()){
		dp[x]=dist[x];
		return;
	}

	long long mins=inf,maxs=-inf;
	for(int i=0;i<v[x].size();i++){
		solve(v[x][i].first,len,v[x][i].second);

		mins=min(mins,v[x][i].second);
		maxs=max(maxs,v[x][i].second);
	}

	dp[x]=dp[v[x][0].first]-v[x][0].second;

	for(int i=0;i<v[x].size();i++){
		v[x][i].second=min(maxs,max(mins,len-dp[v[x][i].first]+v[x][i].second));
	}

	dp[x]=dp[x]+v[x][0].second;
}

void poss(int x,long long add){
	for(int i=0;i<v[x].size();i++){
		v[x][i].second+=add;

		if(v[x][i].second<0){
			poss(v[x][i].first,-v[x][i].second);
			v[x][i].second=0;
		}else{
			poss(v[x][i].first,0);
		}
	}

	for(int i=0;i<v[x].size();i++){
		sum+=abs(v[x][i].second-g[x][i].second);
	}
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	n+=m;
	for(int i=2;i<=n;i++){
		cin>>p[i]>>c[i];

		v[p[i]].push_back({i,c[i]});
		g[p[i]].push_back({i,c[i]});
	}

	dfs(1,0);

	ans=inf;
	for(long long len:dists){

		for(int i=1;i<=n;i++)v[i]=g[i];
		sum=0;
		solve(1,len,0);
		poss(1,0);
		
		ans=min(ans,sum);
	}

	cout<<ans<<"\n";

    return 0;
}

Compilation message

fireworks.cpp: In function 'void dfs(int, long long int)':
fireworks.cpp:20:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
fireworks.cpp: In function 'void solve(int, long long int, long long int)':
fireworks.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
fireworks.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
fireworks.cpp: In function 'void poss(int, long long int)':
fireworks.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
fireworks.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 7 ms 14428 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 6 ms 14424 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 6 ms 14428 KB Output is correct
7 Correct 9 ms 14416 KB Output is correct
8 Correct 6 ms 14600 KB Output is correct
9 Correct 6 ms 14428 KB Output is correct
10 Correct 6 ms 14428 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14428 KB Output is correct
2 Incorrect 6 ms 14584 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 7 ms 14428 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 6 ms 14424 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 6 ms 14428 KB Output is correct
7 Correct 9 ms 14416 KB Output is correct
8 Correct 6 ms 14600 KB Output is correct
9 Correct 6 ms 14428 KB Output is correct
10 Correct 6 ms 14428 KB Output is correct
11 Correct 7 ms 14428 KB Output is correct
12 Incorrect 6 ms 14584 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 7 ms 14428 KB Output is correct
3 Correct 6 ms 14428 KB Output is correct
4 Correct 6 ms 14424 KB Output is correct
5 Correct 6 ms 14428 KB Output is correct
6 Correct 6 ms 14428 KB Output is correct
7 Correct 9 ms 14416 KB Output is correct
8 Correct 6 ms 14600 KB Output is correct
9 Correct 6 ms 14428 KB Output is correct
10 Correct 6 ms 14428 KB Output is correct
11 Correct 7 ms 14428 KB Output is correct
12 Incorrect 6 ms 14584 KB Output isn't correct
13 Halted 0 ms 0 KB -