이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define FOR(i, s, e) for(int i = s; i < e; i++)
#define REP(i, n) for(int i = 0; i < n; i++)
#define all(v) v.begin(), v.end()
#define fir first
#define sec second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
vll x;
vvi c;
vll v;
vpll res;
ll dfs(int a) {
ll sum = x[a];
int l = c[a].size();
REP(i, l) {
sum += dfs(c[a][i]);
}
return max(sum, 0ll);
}
void dfs2(int a, ll pr,ll mp, ll lo) {
ll nex = pr + v[a];
if(nex > mp) {
res.push_back({lo-mp, nex-mp});
}
REP(i, int(c[a].size())) {
dfs2(c[a][i], nex, max(mp, nex), min(lo, nex));
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, a;
ll s;
cin>>n>>s;
x.resize(n+1);
c.resize(n+1);
v.resize(n+1);
x[0] = 0ll;
FOR(i, 1, n+1) {
cin>>x[i]>>a;
c[a].push_back(i);
}
if(s == 1e18) {
cout<<dfs(0);
}
else {
ll ans = 0;
REP(i, int(c[0].size())) {
dfs2(c[0][i], 0ll, 0ll, 0ll);
}
sort(all(res), greater<pll>());
REP(i, int(res.size())) {
if(res[i].fir + s < 0) {
break;
}
s += res[i].sec;
ans += res[i].sec;
}
cout << ans;
}
}
# | 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... |