oj.uz

답안 #386018

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -