제출 #1312255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312255		blackscreen1	Jobs (BOI24_jobs)	C++20	100 / 100	382 ms	93064 KiB

Main

#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, a[300005];
vector<ll> adj[300005];
multiset<pll> ms[300005];
void dfs(ll nd) {
	for (auto it : adj[nd]) {
		dfs(it);
		if (ms[nd].size() < ms[it].size()) {
			swap(ms[nd], ms[it]);
		}
		for (auto it2 : ms[it]) {
			ms[nd].insert(it2);
			auto it3 = ms[nd].find(it2);
			if (it3 != ms[nd].begin()) {
				it3--;
				auto it4 = it3;
				it4++;
				ll tm = (*it3).second;
				while (it4 != ms[nd].end() && (*it3).first + tm >= (*it4).first) {
					auto it5 = it4;
					tm += (*it4).second;
					it4++;
					ms[nd].erase(it5);
				}
				if (tm > (*it3).second) {
					ms[nd].insert({(*it3).first, tm});
					ms[nd].erase(it3);
				}
			}
			it3 = ms[nd].find(it2);
			if (it3 != ms[nd].end()) {
				auto it4 = it3;
				it4++;
				ll tm = (*it3).second;
				while (it4 != ms[nd].end() && (*it3).first + tm >= (*it4).first) {
					auto it5 = it4;
					tm += (*it4).second;
					it4++;
					ms[nd].erase(it5);
				}
				if (tm > (*it3).second) {
					ms[nd].insert({(*it3).first, tm});
					ms[nd].erase(it3);
				}
			}
		}
	}
	pll cs = {max(-a[nd], 0LL), a[nd]};
	while (ms[nd].size() && (cs.second < 0 || cs.second + cs.first >= (*ms[nd].begin()).first)) {
		cs.first = max(cs.first, (*ms[nd].begin()).first - cs.second);
		cs.second += (*ms[nd].begin()).second;
		ms[nd].erase(ms[nd].begin());
	}
	if (cs.second >= 0) ms[nd].insert(cs);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> a[0];
	ll t1;
	iloop(1, n+1) {
		cin >> a[i] >> t1;
		adj[t1].push_back(i);
	}
	dfs(0);
	cout << ((ms[0].size() && (*ms[0].begin()).first == 0) ? ((*ms[0].begin()).second - a[0]) : 0);
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31