# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1043281 | guagua0407 | Jobs (BOI24_jobs) | C++17 | 2057 ms | 27860 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
const int mxn=3e5+5;
vector<int> adj[mxn];
vector<ll> x(mxn);
vector<ll> mn(mxn);
vector<ll> pre(mxn);
vector<bool> used(mxn);
void dfs(int v,int p=-1){
if(p!=-1 and !used[v]){
pre[v]=pre[p]+x[v];
mn[v]=min(mn[p],pre[v]);
}
else{
mn[v]=pre[v]=0;
}
for(auto u:adj[v]){
dfs(u,v);
}
}
int main() {_
int n;
ll S;
cin>>n>>S;
vector<int> p(mxn);
for(int i=1;i<=n;i++){
cin>>x[i]>>p[i];
adj[p[i]].push_back(i);
}
ll prv=S;
while(true){
dfs(0);
int mx=-1;
for(int i=0;i<n;i++){
if(used[i]) continue;
if(S+mn[i]>=0 and (mx==-1 or pre[i]>pre[mx])){
mx=i;
}
}
if(mx==-1 or pre[mx]<0) break;
S+=pre[mx];
//cout<<mx<<' '<<S<<'\n';
while(!used[mx]){
used[mx]=true;
mx=p[mx];
}
}
cout<<S-prv<<'\n';
return 0;
}
//maybe its multiset not set
//yeeorz
//laborz
Compilation message (stderr)
# | 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... |