제출 #1312197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312197		blackscreen1	Jobs (BOI24_jobs)	C++20	100 / 100	339 ms	105924 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);
	}
	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