Submission #916327

#	Time	Username	Problem	Language	Result	Execution time	Memory
916327		manizare	Fireworks (APIO16_fireworks)	C++14	100 / 100	257 ms	83664 KiB

fireworks

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")


#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cerr<<#x << " : " << x << "\n"; 

using namespace std ;   
const int maxn = 4e5 + 10 ,  mod = 1e9 + 7 , inf =1e14  ;
int pr[maxn] , ted[maxn] ;
vector <int> G[maxn] ;
int W[maxn] ;
priority_queue <int> q[maxn] ;
int N, M; 
void dfs(int v) {
	if(v<N) {
		for(int u:G[v]) {
			dfs(u);
			if(q[v].size()<q[u].size()) swap(q[v], q[u]);
			while(q[u].size()) q[v].push(q[u].top()), q[u].pop();
		}
		rep(j, 1, G[v].size()-1) q[v].pop();
		int x=q[v].top()+W[v]; q[v].pop();
		int y=q[v].top()+W[v]; q[v].pop();
		q[v].push(x), q[v].push(y);
	} else q[v].push(W[v]), q[v].push(W[v]);
}
signed main(){
    ios::sync_with_stdio(0) ;cin.tie(0);
	int r=0;
	cin>>N>>M;
	rep(i, 1, N+M-1) {
		int j;
		cin>>j>>W[i];
		G[j-1].pb(i);
		r+=W[i];
	}
    dfs(0);
    int p=q[0].top(), k=0; q[0].pop();
	while(q[0].size()){
		r-=k++*(p-q[0].top()), p=q[0].top(), q[0].pop();
    }
    cout<<r-k*p;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(long long int)':
fireworks.cpp:12:38: 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]
   12 | #define rep(i , a , b) for(int i=a;i <= (b);i++)
      |                                      ^
fireworks.cpp:30:3: note: in expansion of macro 'rep'
   30 |   rep(j, 1, G[v].size()-1) q[v].pop();
      |   ^~~

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45