제출 #1190423

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190423		Mer123haba456	Jobs (BOI24_jobs)	C++20	29 / 100	188 ms	73880 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define N lli(2e6)
#define heps(v) v.begin(), v.end()
typedef long long int lli;
typedef std::vector<lli> vlli;
typedef pair<lli, lli> plli;
typedef pair<lli, plli> pplli;
typedef std::vector<plli> vplli;
typedef set<lli> slli;
typedef map<lli, lli> mlli;

lli n, t, k, q, m;
string str;
vlli vect;
vlli gr[N];
plli diz[N];
lli par[N];

priority_queue<plli> Q;

void dfs(lli v){
    if(par[v] != 0)
        return;
    par[v] = -1;
    diz[v].first += vect[v];
    diz[v].second = min(diz[v].second, diz[v].first);
    if(diz[v].first >= 0){
        Q.push({diz[v].second, v});
        return;
    }
    for(lli go: gr[v]){
        par[go]--;
        diz[go].second = min(diz[go].second, diz[v].second);
        diz[go].first += diz[v].first;
        dfs(go);
    }
}

int main()
{
    cin >> n >> k;
    lli kilk = k;
    vect.push_back(0); 
    for(lli i = 1;i<=n;i++){
        cin >> m >> q;
        vect.push_back(m);
        if(q > 0){
            gr[q].push_back(i);
            par[i]++;
        }
    }
    for(lli i = 1;i<=n;i++)
        dfs(i);
    while(!(Q.empty()) && (-Q.top().first <= k)){
        plli su = Q.top();
        Q.pop();
        k += diz[su.second].first;
        for(lli go:gr[su.second]){
            par[go]--;
            dfs(go);
        }
    }
    cout << (k - kilk) << endl;
}

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