oj.uz

답안 #997650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
997650 2024-06-12T16:05:14 Z salmon Jobs (BOI24_jobs) C++14
0 / 100
 241 ms 85072 KB 
#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> root;
int h,h1;
vector<int> adjlst[300100];
long long int lst[300100];
int parent[300100];
const long long int inf = 2e18;
long long int money;
priority_queue<pair<long long int,long long int>,vector<pair<long long int,long long int>>,greater<pair<long long int,long long int>>> pq;
set<pair<long long int, long long int>> k;

pair<set<pair<long long int,long long int>>*,long long int> dfs(int i){
//printf("%d",i);
    pair<int,int> ii = {-1,-1};
    vector<pair<set<pair<long long int,long long int>>*,long long int>> v;

    for(int j : adjlst[i]){
        v.push_back(dfs(j));

        ii = max({(int)(v.back().first -> size()),v.size() - 1},ii);
    }
//printf("%d",i);
    set<pair<long long int,long long int>>* sat;
    long long int offset = 0;
    long long int va = lst[i];
    long long int other = max(0LL,-lst[i]);

    if(ii.first == -1){
        sat = new set<pair<long long int,long long int>>();
        if(lst[i] > 0) sat -> insert({max(other,-lst[i]),lst[i]});
    }
    else{
        sat = v[ii.second].first;
        offset = v[ii.second].second;
        if(lst[i] > 0) sat -> insert({-lst[i] - offset,lst[i]});
    }


    for(int i = 0; i < v.size(); i++){
        if(i == ii.second) continue;
        for(pair<long long int, long long int> pp : *(v[i].first) ){
            pp.first = pp.first + v[i].second - offset;
            sat -> insert(pp);
        }
    }

    offset -= va;
    long long int num = 0;

    while(sat -> lower_bound({-offset + other,inf}) != sat -> begin()){
        auto it = sat -> lower_bound({-offset + other,inf});
        advance(it,-1);
        num += it -> second;
        sat -> erase(it);
    }

    if(num != 0) sat -> insert({-offset + other, num});

    num = -lst[i];
    if(lst[i] < 0){
        while(num != 0 && !(sat -> empty())){
            auto it = sat -> begin();
            long long int temp = min(num, it -> second);
            num -= temp;
            if(it -> second == temp){
                sat -> erase(it);
            }
            else{
                pair<long long int, long long int> ii = *it;
                ii.second = ii.second - temp ;
                sat -> erase(it);
                sat -> insert(ii);
            }
        }
    }

    return {sat,offset};
}

int main(){
	scanf(" %d",&N);
    scanf(" %lld",&money);

    long long int init = money;

	for(int i = 1; i <= N; i++){
		scanf(" %d",&h);
		scanf(" %d",&h1);

		if(h1 == 0){
			root.push_back(i);
		}
		else{
            adjlst[h1].push_back(i);
		}
		lst[i] = h;
	}

	for(int i : root){
        pair<set<pair<long long int,long long int>>*,long long int> ii = dfs(i);

        for(pair<long long int, long long int> pp : *(ii.first)){
            pp.first += ii.second;
            pq.push(pp);
        }
	}

	while(!pq.empty()){
        if(money < pq.top().first) break;
        money += pq.top().second;
        pq.pop();
	}

	printf("%lld",money - init);
}
/*
6 1
3 0
-3 1
-5 0
2 1
6 3
-4 5

*/

Compilation message

Main.cpp: In function 'std::pair<std::set<std::pair<long long int, long long int> >*, long long int> dfs(int)':
Main.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::set<std::pair<long long int, long long int> >*, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  scanf(" %d",&N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf(" %lld",&money);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |   scanf(" %d",&h);
      |   ~~~~~^~~~~~~~~~
Main.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   scanf(" %d",&h1);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 241 ms 85072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 10840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 241 ms 85072 KB Output isn't correct
2 Halted 0 ms 0 KB -