oj.uz

Submission #386018

# Submission time Handle Problem Language Result Execution time Memory
386018 2021-04-05T12:26:07 Z grt Fireworks (APIO16_fireworks) C++17
7 / 100
 11 ms 14444 KB 
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 300 * 1000 + 10;
const ll INF = 1e18;
int n, m;
int p[nax], v[nax];
int in[nax];
queue<int>Q;
bool leaf[nax];
pair<ll,ll> f[nax], d[nax];
multiset<ll>S[nax];

int main() {
	cin >> n >> m;
	for(int i = n; i < n + m; ++i) leaf[i] = true;
	n += m;
	for(int i = 1; i < n; ++i) {
		cin >> p[i] >> v[i];
		p[i]--;
		in[p[i]]++;
	}
	for(int i = 0; i < n; ++i) {
		if(in[i] == 0) {
			Q.push(i);
		}
	}
	while(!Q.empty()) {
		int x = Q.front();
		Q.pop();
		//~ if(x == 0) break;
		if(leaf[x]) {
			d[x] = {v[x], v[x]};
			f[x] = {1, -v[x]};
		}
			while(f[x].ST > 1) {
				auto it = S[x].end();
				it--;
				f[x].ST--;
				f[x].ND += (*it);
				S[x].erase(it);
			}
			if((int)S[x].size() > 0) {
			auto it = S[x].end();
			it--;
			d[x].ND = (*it);
			it--;
			d[x].ST = (*it);
			S[x].clear();
			d[x].ST += v[x];
			d[x].ND += v[x];
			f[x].ND -= v[x];
		}
		//~ cout << x << ": " << d[x].ST << " " << d[x].ND << "\n";
		if(x == 0) break;
		in[p[x]]--;
		S[p[x]].insert(d[x].ST);
		S[p[x]].insert(d[x].ND);
		f[p[x]].ST += f[x].ST;
		f[p[x]].ND += f[x].ND;
		if(in[p[x]] == 0) {
			Q.push(p[x]);
		}
	}
	// -2 3
	//~ cout << f[0].ST << " " << f[0].ND << "\n";
	cout << f[0].ND + d[0].ND;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 11 ms 14444 KB Output is correct
6 Correct 11 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 11 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 11 ms 14444 KB Output is correct
6 Correct 11 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 11 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 10 ms 14444 KB Output is correct
12 Correct 11 ms 14444 KB Output is correct
13 Incorrect 10 ms 14444 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 11 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 11 ms 14444 KB Output is correct
6 Correct 11 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 11 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 10 ms 14444 KB Output is correct
12 Correct 11 ms 14444 KB Output is correct
13 Incorrect 10 ms 14444 KB Output isn't correct
14 Halted 0 ms 0 KB -