oj.uz

Submission #211810

# Submission time Handle Problem Language Result Execution time Memory
211810 2020-03-21T11:19:21 Z kig9981 Fireworks (APIO16_fireworks) C++17
0 / 100
 14 ms 16768 KB 
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;

struct Splay
{
	int p, l, r, c;
	long long A, B, v, M, lA, lB;
};

vector<pair<int,int>> adj[300000];
int parent[300000], W[300000], C[300000];
long long B[300000];
priority_queue<long long> Q[300000];

int prep(int c)
{
	W[C[c]=c]=1;
	for(auto[n,w]: adj[c]) W[c]+=prep(n);
	for(auto &n: adj[c]) if(W[adj[c][0].first]<W[n.first]) swap(adj[c][0],n);
	if(adj[c].size()) C[c]=C[adj[c][0].first];
	return W[c];
}

void solve(int c)
{
	long long t1, t2;
	if(C[c]==c) {
		Q[c].push(0); Q[c].push(0);
		return;
	}
	for(auto[n,w]: adj[c]) {
		solve(n);
		t1=Q[C[n]].top(); Q[C[n]].pop();
		t2=Q[C[n]].top(); Q[C[n]].pop();
		Q[C[n]].push(t1+w); Q[C[n]].push(t2+w);
		B[C[n]]+=w;
		if(C[c]!=C[n]) {
			B[C[c]]+=B[C[n]];
			while(!Q[C[n]].empty()) {
				Q[C[c]].push(Q[C[n]].top());
				Q[C[n]].pop();
			}
			Q[C[c]].pop();
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M;
	stack<long long> res;
	long long ans, x=0;
	cin>>N>>M; N+=M;
	for(int i=1;i<N;i++) {
		int c;
		cin>>parent[i]>>c;
		adj[--parent[i]].emplace_back(i,c);
	}
	prep(0); solve(0);
	M=1-Q[C[0]].size(); ans=B[C[0]];
	while(Q[C[0]].size()) {
		res.push(Q[C[0]].top());
		Q[C[0]].pop();
	}
	while(res.size()) {
		ans+=(res.top()-x)*M++;
		x=res.top();
		res.pop();
	}
	cout<<ans<<'\n';
	return 0;
}

Compilation message

fireworks.cpp: In function 'int prep(int)':
fireworks.cpp:27:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) W[c]+=prep(n);
              ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16768 KB Output is correct
2 Incorrect 13 ms 16768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16768 KB Output is correct
2 Correct 14 ms 16768 KB Output is correct
3 Incorrect 14 ms 16768 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16768 KB Output is correct
2 Incorrect 13 ms 16768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16768 KB Output is correct
2 Incorrect 13 ms 16768 KB Output isn't correct
3 Halted 0 ms 0 KB -