이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 61
const ll MOD = 1e9 + 7;
const ll MAXN = 3e5 + 100;
#define int long long
vector<vector<int>> graph;
set<pair<int,int>> st[MAXN];
ll val[MAXN];
void dfs(int node) {
for (auto u : graph[node]) {
dfs(u);
if (st[node].size() < st[u].size())
swap(st[node], st[u]);
for (auto v : st[u])
st[node].insert(v);
}
if (val[node] >= 0)
st[node].insert({0, val[node]});
else if (graph[node].size()) {
int req = val[node], now = val[node];
// sete ekleyebilmek için now >= 0 olmalı
while (st[node].size() && (now < 0 || st[node].begin()->f <= -req)) {
pair<int,int> Q = *st[node].begin();
st[node].erase(st[node].begin());
if (now < 0)
req = min(req, now - Q.f);
now += Q.s;
}
if (now >= 0)
st[node].insert({-req, now});
}
}
signed main() {
fast
ll N, s, p;
cin >> N >> s;
graph = vector<vector<int>>(N+1, vector<int>());
for (int i = 1; i <= N; i++) {
cin >> val[i] >> p;
graph[p].push_back(i);
}
dfs(0);
ll old = s;
for (auto u : st[0]) {
if (s >= u.f)
s += u.s;
}
cout << s - old << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |