oj.uz

Submission #1092673

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

const long long inf=1e13;

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

long long ans;

vector<long long> dists[5007];
vector<long long> dp[5007];
vector<bool> li[5007];

void dfs(int x,long long d){
	if(v[x].empty()){
		dists[x]={0};
		return;
	}

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

		for(long long f:dists[v[x][i].first])dists[x].push_back(f+v[x][i].second);
	}

	dp[x].resize(dists[x].size());
	li[x].resize(dists[x].size());
}

long long solve(int x,int len){
	if(v[x].empty())return 0;

	if(li[x][len])return dp[x][len];
	li[x][len]=true;

	for(int i=0;i<v[x].size();i++){
		
		long long mins=inf;
		for(int f=0;f<dists[v[x][i].first].size();f++){
			if(dists[x][len]-dists[v[x][i].first][f]>=0){
				mins=min(mins,abs(v[x][i].second-(dists[x][len]-dists[v[x][i].first][f]) )+solve(v[x][i].first,f));
			}
		}

		dp[x][len]+=mins;
	}

	return dp[x][len];
}

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]});
	}

	dfs(1,0);

	ans=inf;
	for(int len=0;len<dists[1].size();len++){
		ans=min(ans,solve(1,len));
	}

	cout<<ans<<"\n";

    return 0;
}

Compilation message

fireworks.cpp: In function 'void dfs(int, long long int)':
fireworks.cpp:23:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
fireworks.cpp: In function 'long long int solve(int, int)':
fireworks.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~
fireworks.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int f=0;f<dists[v[x][i].first].size();f++){
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:71:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int len=0;len<dists[1].size();len++){
      |                ~~~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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