oj.uz

Submission #933271

# Submission time Handle Problem Language Result Execution time Memory
933271 2024-02-25T11:09:26 Z amirhoseinfar1385 Fireworks (APIO16_fireworks) C++17
26 / 100
 10 ms 29020 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=300000+10;
vector<long long>adj[maxn];
pair<long long,long long>par[maxn];
long long n;
long long sum=0;

void vorod(){
	long long d;
	cin>>n>>d;
	n+=d;
	for(long long i=2;i<=n;i++){
		cin>>par[i].first>>par[i].second;
		adj[par[i].first].push_back(i);
		sum+=par[i].second;
	}
}
priority_queue<long long>pq[maxn];
priority_queue <int,vector<int>, greater<int>>revpq[maxn];
long long val[maxn];
void add(long long u,long long x,long long z){
	int ps=pq[u].top(),nx=revpq[u].top();
	if(z==0){
		if(x<=nx){
			pq[u].push(x);
		}
		else{
			pq[u].push(revpq[u].top());
			revpq[u].pop();
			revpq[u].push(x);
		}
	}
	else{
		if(x>=ps){
			revpq[u].push(x);
		}
		else{
			revpq[u].push(pq[u].top());
			pq[u].pop();
			pq[u].push(x);
		}
	}
}

void merge(long long u,long long v){
	long long fu=u;
	if(pq[u].size()+revpq[u].size()<pq[v].size()+revpq[u].size()){
		swap(u,v);
	}
	while(pq[v].size()>0){
		add(u,pq[v].top()+val[v]-val[u],0);
		pq[v].pop();
	}
	while(revpq[v].size()>0){
		add(u,revpq[v].top()+val[v]-val[u],1);
		revpq[v].pop();
	}
	if(u!=fu){
		swap(pq[u],pq[v]);
		swap(revpq[u],revpq[v]);
		swap(val[u],val[v]);
	}
}

void solve(long long u,long long len=0){
	if(u!=1){
		len+=par[u].second;
	}
	for(auto x:adj[u]){
		solve(x,len);
		merge(u,x);
	}
	if((long long)adj[u].size()==0){
		pq[u].push(len);
		revpq[u].push(len);
	}
	if(u!=1){
		val[u]-=par[u].second;
		int hey=revpq[u].top();
		while(revpq[u].size()>0){
			revpq[u].pop();
		}
		revpq[u].push(hey+par[u].second);
		hey=pq[u].top();
		pq[u].pop();
		pq[u].push(hey+par[u].second);
	}
	return ;
}

void khor(){
	//cout<<"suma: "<<sum<<" "<<val[1]<<endl;
	vector<long long>all;
	while((long long)pq[1].size()>0){
		all.push_back(pq[1].top()+val[1]);
		//cout<<pq[1].top()+val[1]<<endl;
		pq[1].pop();
	}
	all.push_back(0);
	long long res=sum;
	long long sz=all.size();
	for(long long i=0;i<sz-1;i++){
		////cout<<"tof: "<<all[i]<<" "<<i<<" "<<(all[i]-all[i+1])*i<<endl;
		res-=(all[i]-all[i+1])*((i+1));
	}
	cout<<res<<endl;
}	

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	vorod();
	solve(1);
	khor();
}

Subtask #1
7.0 / 7.0

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

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29020 KB Output is correct
2 Correct 7 ms 29020 KB Output is correct
3 Correct 7 ms 29020 KB Output is correct
4 Correct 7 ms 29000 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 7 ms 29020 KB Output is correct
7 Correct 6 ms 29020 KB Output is correct
8 Correct 10 ms 29020 KB Output is correct
9 Correct 7 ms 29016 KB Output is correct
10 Correct 8 ms 29020 KB Output is correct
11 Correct 6 ms 29020 KB Output is correct
12 Correct 7 ms 29020 KB Output is correct
13 Correct 7 ms 29020 KB Output is correct
14 Correct 6 ms 29020 KB Output is correct
15 Correct 7 ms 29020 KB Output is correct
16 Correct 6 ms 29020 KB Output is correct
17 Correct 7 ms 29020 KB Output is correct
18 Correct 8 ms 29020 KB Output is correct
19 Correct 7 ms 29020 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29020 KB Output is correct
2 Correct 9 ms 29020 KB Output is correct
3 Correct 7 ms 29020 KB Output is correct
4 Correct 8 ms 29016 KB Output is correct
5 Correct 7 ms 29020 KB Output is correct
6 Correct 8 ms 29012 KB Output is correct
7 Correct 7 ms 29020 KB Output is correct
8 Correct 8 ms 29020 KB Output is correct
9 Correct 7 ms 28996 KB Output is correct
10 Correct 7 ms 29020 KB Output is correct
11 Correct 6 ms 29020 KB Output is correct
12 Correct 7 ms 29020 KB Output is correct
13 Correct 7 ms 29020 KB Output is correct
14 Correct 7 ms 29000 KB Output is correct
15 Correct 6 ms 29020 KB Output is correct
16 Correct 7 ms 29020 KB Output is correct
17 Correct 6 ms 29020 KB Output is correct
18 Correct 10 ms 29020 KB Output is correct
19 Correct 7 ms 29016 KB Output is correct
20 Correct 8 ms 29020 KB Output is correct
21 Correct 6 ms 29020 KB Output is correct
22 Correct 7 ms 29020 KB Output is correct
23 Correct 7 ms 29020 KB Output is correct
24 Correct 6 ms 29020 KB Output is correct
25 Correct 7 ms 29020 KB Output is correct
26 Correct 6 ms 29020 KB Output is correct
27 Correct 7 ms 29020 KB Output is correct
28 Correct 8 ms 29020 KB Output is correct
29 Correct 7 ms 29020 KB Output is correct
30 Incorrect 7 ms 29020 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29020 KB Output is correct
2 Correct 9 ms 29020 KB Output is correct
3 Correct 7 ms 29020 KB Output is correct
4 Correct 8 ms 29016 KB Output is correct
5 Correct 7 ms 29020 KB Output is correct
6 Correct 8 ms 29012 KB Output is correct
7 Correct 7 ms 29020 KB Output is correct
8 Correct 8 ms 29020 KB Output is correct
9 Correct 7 ms 28996 KB Output is correct
10 Correct 7 ms 29020 KB Output is correct
11 Correct 6 ms 29020 KB Output is correct
12 Correct 7 ms 29020 KB Output is correct
13 Correct 7 ms 29020 KB Output is correct
14 Correct 7 ms 29000 KB Output is correct
15 Correct 6 ms 29020 KB Output is correct
16 Correct 7 ms 29020 KB Output is correct
17 Correct 6 ms 29020 KB Output is correct
18 Correct 10 ms 29020 KB Output is correct
19 Correct 7 ms 29016 KB Output is correct
20 Correct 8 ms 29020 KB Output is correct
21 Correct 6 ms 29020 KB Output is correct
22 Correct 7 ms 29020 KB Output is correct
23 Correct 7 ms 29020 KB Output is correct
24 Correct 6 ms 29020 KB Output is correct
25 Correct 7 ms 29020 KB Output is correct
26 Correct 6 ms 29020 KB Output is correct
27 Correct 7 ms 29020 KB Output is correct
28 Correct 8 ms 29020 KB Output is correct
29 Correct 7 ms 29020 KB Output is correct
30 Incorrect 7 ms 29020 KB Output isn't correct
31 Halted 0 ms 0 KB -