oj.uz

Submission #1015300

# Submission time Handle Problem Language Result Execution time Memory
1015300 2024-07-06T08:30:37 Z vjudge1 Fireworks (APIO16_fireworks) C++17
7 / 100
 4 ms 7260 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
int const N=3e5+5;
int const mod=1e9+7;

vector<int> child[N];
pair<int,int> val[N];
int par[N],len[N];
int cost=0;
void dfs(int node){
	vector<int> v;
	for(int i:child[node]){
		dfs(i);
		v.push_back(val[i].first+len[i]);
		v.push_back(val[i].second+len[i]);
	}
	if(v.size()==0)
		return;
	// cout<<"Node := "<<node<<endl;
	int opt=1e15;
	vector<int> a;
	for(int i=0;i<v.size();i++){
		// cout<<v[i]<<' ';
		int t=0;
		for(int c:child[node])
			t+=min(abs((val[c].first+len[c])-v[i]),abs((val[c].second+len[c])-v[i]));
		if(t>opt)
			continue;
		else if(t<opt){
			opt=t;
			val[node].first=v[i];
			val[node].second=v[i];
		}
		else
			val[node].second=v[i];
	}
	// cout<<endl;
	cost+=opt;
	// cout<<opt<<endl;
}
signed main(){
	int n,m;
	cin>>n>>m;
	for (int i = 2; i <=n+m; ++i)
	{
		cin>>par[i]>>len[i];
		child[par[i]].push_back(i);
	}
	dfs(1);
	cout<<cost<<endl;
	return 0;
}

Compilation message

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

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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