oj.uz

Submission #1092455

# Submission time Handle Problem Language Result Execution time Memory
1092455 2024-09-24T06:41:11 Z alexander707070 Fireworks (APIO16_fireworks) C++14
7 / 100
 2 ms 2652 KB 
#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const long long inf=1e17;

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

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

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

	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];
		sum[x]+=sum[v[x][i].first]+v[x][i].second*sz[v[x][i].first];
	}
}

long long solve(int x,long long len,long long e){
	long long res=0;
	long long diff=sum[x]+sz[x]*e-sz[x]*len;
	
	if(diff<-sz[x]/2){
		res+=-(diff+sz[x]/2)/sz[x]+((diff+sz[x]/2)%sz[x]!=0);
		e+=-(diff+sz[x]/2)/sz[x]+((diff+sz[x]/2)%sz[x]!=0);
	}

	if(diff>sz[x]/2){
		res+=min(e,(diff-sz[x]/2)/sz[x]+((diff-sz[x]/2)%sz[x]!=0));
		e-=min(e,(diff-sz[x]/2)/sz[x]+((diff-sz[x]/2)%sz[x]!=0));
	}

	for(int i=0;i<v[x].size();i++){
		res+=solve(v[x][i].first,len-e,v[x][i].second);
	}

	return res;
}

int main(){
	
	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]});
	}

	dfs(1,0);

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

		long long curr=0;
		for(int i=0;i<v[1].size();i++){
			curr+=solve(v[1][i].first,len,v[1][i].second);
		}
		
		ans=min(ans,curr);
	}

	cout<<ans<<"\n";

    return 0;
}

Compilation message

fireworks.cpp: In function 'void dfs(int, long long int)':
fireworks.cpp:19: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]
   19 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
fireworks.cpp: In function 'long long int solve(int, long long int, long long int)':
fireworks.cpp:41: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]
   41 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:63:16: 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]
   63 |   for(int i=0;i<v[1].size();i++){
      |               ~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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