oj.uz

답안 #933236

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933236 2024-02-25T10:01:00 Z amirhoseinfar1385 Fireworks (APIO16_fireworks) C++17
0 / 100
 4 ms 19644 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];
long long val[maxn];
void add(long long u,long long x,long long z){
	//cout<<"wtf: "<<u<<" "<<x<<endl;
	long long nx=pq[u].top();
	pq[u].pop();
	long long ps=pq[u].top();
	pq[u].push(nx);
	if(z==0){
		if(x<=nx){
			pq[u].pop();
			pq[u].push(x);
			return ;
		}
		return ;
	}
	pq[u].push(x);
}

void merge(long long u,long long v){
	long long fu=u;
	if(pq[u].size()<pq[v].size()){
		swap(u,v);
	}
	long long z=0;
	while(pq[v].size()>0){
		auto x=pq[v].top();
		pq[v].pop();
		//cout<<u<<" "<<v<<" "<<val[u]<<" "<<val[v]<<" "<<x<<" tof"<<endl;
		x+=val[v];
		x-=val[u];
		if(z<2){
			add(u,x,z);
			z++;
		}
		else{
			pq[u].push(x);
		}
	}
	if(u!=fu){
		swap(pq[u],pq[fu]);
		swap(val[u],val[fu]);
	}
}

void solve(long long u,long long len=0){
	if(u!=1){
		len+=par[u].second;
	}
	//cout<<"injy: "<<u<<" "<<len<<endl;
	for(auto x:adj[u]){
		solve(x,len);
		merge(u,x);
	}
	//cout<<"tamam: "<<u<<endl;
	if((long long)adj[u].size()==0){
		pq[u].push(len);
		pq[u].push(len);
	}
	//cout<<"khor: "<<u<<endl;
//	priority_queue<long long>qp=pq[u];
//	while(qp.size()>0){
		//cout<<qp.top()+val[u]<<" ";
//		qp.pop();
//	}
	//cout<<"\n";
	if(u!=1){
		long long f=pq[u].top();
		pq[u].pop();
		long long ff=pq[u].top();
		pq[u].pop();
		val[u]-=par[u].second;
		pq[u].push(ff+par[u].second);
		pq[u].push(f+par[u].second);
	}
	//cout<<"khor: "<<u<<endl;
//	qp=pq[u];
//	while(qp.size()>0){
		//cout<<qp.top()+val[u]<<" ";
//		qp.pop();
//	}
	//cout<<"\n";
	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);
	}
	cout<<res<<endl;
}	

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

Compilation message

fireworks.cpp: In function 'void add(long long int, long long int, long long int)':
fireworks.cpp:25:12: warning: unused variable 'ps' [-Wunused-variable]
   25 |  long long ps=pq[u].top();
      |            ^~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 19548 KB Output is correct
2 Incorrect 4 ms 19548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 19548 KB Output is correct
2 Correct 4 ms 19548 KB Output is correct
3 Incorrect 4 ms 19644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 19548 KB Output is correct
2 Incorrect 4 ms 19548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 19548 KB Output is correct
2 Incorrect 4 ms 19548 KB Output isn't correct
3 Halted 0 ms 0 KB -