oj.uz

Submission #652850

# Submission time Handle Problem Language Result Execution time Memory
652850 2022-10-24T22:01:07 Z lovrot Fireworks (APIO16_fireworks) C++17
19 / 100
 27 ms 43236 KB 
#include <bits/stdc++.h>

#define X first
#define Y second
#define pb push_back 

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

struct func{
	ll a;
	ll b;
	int ind;
};

const int N = 300010;

int n, m, siz[N];
ll edge[N];

vector<int> g[N];
multiset<ll> slope[N];

func merge(func a, func b){
	func ret;
	ret.a = a.a + b.a;
	ret.b = a.b + b.b;	
	ret.ind = a.ind;
	
	for(auto x : slope[b.ind]) slope[a.ind].insert(x); 
	return ret;
}

func f(int u){
	func ret;
	if(g[u].empty()){
		ret.a = 1;
		ret.b = -edge[u];
		ret.ind = u;
		slope[u].insert(edge[u]);
		slope[u].insert(edge[u]);
		return ret;
	} 
	ret = f(g[u][0]);
	for(int i = 1; i < g[u].size(); i++){
		ret = merge(ret, f(g[u][i]));
	}
	int ind = ret.ind;
	while(ret.a > 1){
		ll last = *slope[ind].rbegin();
		slope[ind].erase(prev(slope[ind].end()));
		ret.b += last;
		ret.a--;
	}
	ll val = *prev(slope[ind].end()) + edge[u];
	slope[ind].erase(prev(slope[ind].end())); 
	ll val2 = *prev(slope[ind].end()) + edge[u];
	slope[ind].erase(prev(slope[ind].end())); 
	ret.b -= edge[u];
	slope[ind].insert(val);
	slope[ind].insert(val2);
	return ret;
}

int dfs(int u){
	int ret = 1;
	for(int v : g[u]){
		ret += dfs(v);
	}
	siz[u] = ret;
	return ret;
}

int main(){
	scanf("%d%d\n", &n, &m);
	
	for(int i = 2; i <= n + m; i++){
		int par, val;
		scanf("%d%d", &par, &val);
		g[par].pb(i);
		edge[i] = val;
	}
	
	dfs(1);
	
	for(int i = 1; i <= n; i++){
		sort(g[i].begin(), g[i].end(), [](int a, int b) -> bool {return siz[a] >= siz[b];});	
	}
	
	func res = f(1);
	ll ans = *slope[res.ind].rbegin() + res.b;
	printf("%lld\n", ans);
	return 0;
}

Compilation message

fireworks.cpp: In function 'func f(int)':
fireworks.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i = 1; i < g[u].size(); i++){
      |                 ~~^~~~~~~~~~~~~
fireworks.cpp: In function 'int main()':
fireworks.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  scanf("%d%d\n", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
fireworks.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   scanf("%d%d", &par, &val);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21404 KB Output is correct
2 Correct 11 ms 21332 KB Output is correct
3 Runtime error 27 ms 43236 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21460 KB Output is correct
2 Correct 11 ms 21460 KB Output is correct
3 Correct 12 ms 21460 KB Output is correct
4 Correct 11 ms 21384 KB Output is correct
5 Correct 12 ms 21460 KB Output is correct
6 Correct 11 ms 21464 KB Output is correct
7 Correct 12 ms 21580 KB Output is correct
8 Correct 11 ms 21452 KB Output is correct
9 Correct 11 ms 21444 KB Output is correct
10 Correct 11 ms 21460 KB Output is correct
11 Correct 11 ms 21460 KB Output is correct
12 Correct 11 ms 21464 KB Output is correct
13 Correct 11 ms 21444 KB Output is correct
14 Correct 10 ms 21460 KB Output is correct
15 Correct 13 ms 21460 KB Output is correct
16 Correct 11 ms 21448 KB Output is correct
17 Correct 11 ms 21444 KB Output is correct
18 Correct 12 ms 21472 KB Output is correct
19 Correct 12 ms 21460 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21404 KB Output is correct
2 Correct 11 ms 21332 KB Output is correct
3 Runtime error 27 ms 43236 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21404 KB Output is correct
2 Correct 11 ms 21332 KB Output is correct
3 Runtime error 27 ms 43236 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -