oj.uz

Submission #377660

# Submission time Handle Problem Language Result Execution time Memory
377660 2021-03-14T15:50:59 Z LucaDantas Fireworks (APIO16_fireworks) C++17
0 / 100
 9 ms 11244 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back

constexpr int maxn = 2e5+10;

vector<int> g[maxn];
priority_queue<long long> changes[maxn];
int c[maxn], start_slope[maxn], n;
long long start_y[maxn];

void combine(int a, int b) {
	auto& q = changes[a];
	start_y[a] += start_y[b];
	start_slope[a] += start_slope[b];
	for(; changes[b].size(); changes[b].pop())
		q.push(changes[b].top());
	while((int)q.size() > -start_slope[a] + 1)
		q.pop();
}

void dfs(int u) {
	if(u >= n) {
		start_slope[u] = -1;
		start_y[u] = c[u];
		changes[u].push((long long)c[u]);
		changes[u].push((long long)c[u]);
	} else {
		int big = g[u][0];
		for(int v : g[u]) {
			if(changes[v].size() > changes[big].size())
				big = v;
			dfs(v);
		}
		swap(changes[u], changes[big]);
		start_slope[u] = start_slope[big];
		start_y[u] = start_y[big];
		for(int v : g[u])
			if(v != big) combine(u, v);
		start_y[u] += (long long)c[u];
		auto& q = changes[u];
		long long a = q.top(); q.pop();
		long long b = q.top(); q.pop();
		q.push(a + c[u]);
		q.push(b + c[u]);
	}
}

int32_t main() {
	int m; scanf("%lld %lld", &n, &m);
	for(int i = 1; i < n+m; i++) {
		int p; scanf("%lld %lld", &p, &c[i]);
		g[p-1].pb(i);
	}
	dfs(0);
	long long ans = start_y[0], last = 0;
	int slope = start_slope[0];
	auto& q = changes[0];
	vector<long long> opa;
	while(q.size())
		opa.pb(q.top()), q.pop();
	while(opa.size()) {
		ans += 1ll * slope * (opa.back() - last);
		last = opa.back(); opa.pop_back();
		++slope;
	}
	printf("%lld\n", ans);
}

Compilation message

fireworks.cpp: In function 'int32_t main()':
fireworks.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |  int m; scanf("%lld %lld", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:54:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |   int p; scanf("%lld %lld", &p, &c[i]);
      |          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Incorrect 9 ms 11244 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Incorrect 9 ms 11244 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Incorrect 9 ms 11244 KB Output isn't correct
3 Halted 0 ms 0 KB -