oj.uz

답안 #386016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
386016 2021-04-05T12:22:04 Z grt Fireworks (APIO16_fireworks) C++17
7 / 100
 13 ms 14464 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;
	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);
			leaf[i] = true;
		}
	}
	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]};
		} else {
			while(f[x].ST > 1) {
				auto it = S[x].end();
				it--;
				f[x].ST--;
				f[x].ND += (*it);
				S[x].erase(it);
			}
			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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 11 ms 14464 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 11 ms 14444 KB Output is correct
5 Correct 11 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Correct 13 ms 14444 KB Output is correct
9 Correct 11 ms 14444 KB Output is correct
10 Correct 11 ms 14444 KB Output is correct

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 11 ms 14444 KB Output is correct
3 Incorrect 11 ms 14444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 11 ms 14464 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 11 ms 14444 KB Output is correct
5 Correct 11 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Correct 13 ms 14444 KB Output is correct
9 Correct 11 ms 14444 KB Output is correct
10 Correct 11 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 11 ms 14444 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 11 ms 14464 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 11 ms 14444 KB Output is correct
5 Correct 11 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 11 ms 14444 KB Output is correct
8 Correct 13 ms 14444 KB Output is correct
9 Correct 11 ms 14444 KB Output is correct
10 Correct 11 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 11 ms 14444 KB Output isn't correct
14 Halted 0 ms 0 KB -