oj.uz

Submission #998069

# Submission time Handle Problem Language Result Execution time Memory
998069 2024-06-13T09:18:01 Z salmon Jobs (BOI24_jobs) C++14
14 / 100
 256 ms 85380 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>>* dfs(int i){
//printf("%d",i);
    pair<int,int> ii = {-1,-1};
    vector<set<pair<long long int,long long int>>*> v;

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

        ii = max({(int)(v.back() -> size()),v.size() - 1},ii);
    }
//printf("%d\n",i);
    set<pair<long long int,long long int>>* sat;
    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({0,lst[i]});
    }
    else{
        sat = v[ii.second];
        if(lst[i] > 0) sat -> insert({0,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]) ){
            pp.first = pp.first;
            sat -> insert(pp);
        }
    }

    //offset -= min(0LL,va);
    long long int num = 0;

    if(lst[i] < 0){
        long long int balls = -lst[i];

        num = -lst[i];
        while(num != 0 && !(sat -> empty())){
            auto it = sat -> begin();
            long long int temp = min(num, it -> second);
            balls = max((sat -> begin() -> first) - ((-lst[i]) - num) + -lst[i], balls);
            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);
            }
        }

        if(num != 0) return {sat};

        other = balls;
    }

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

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

    return sat;
}

int main(){
    //freopen("jobs.17-2345.in","r",stdin);

	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;
	}
	//printf("\n");

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

        for(pair<long long int, long long int> pp : *ii){
            //printf("%d %d\n",pp.first,pp.second);
            pq.push(pp);
        }
	}

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

	printf("%lld",money - init);
}
/*
5 104
-103 0
102 1
-103 2
55 3
50 3


*/

Compilation message

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 85380 KB Output is correct
2 Correct 175 ms 54972 KB Output is correct
3 Correct 115 ms 37412 KB Output is correct
4 Correct 155 ms 49696 KB Output is correct
5 Correct 142 ms 62336 KB Output is correct
6 Incorrect 118 ms 44244 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 11100 KB Output is correct
12 Correct 2 ms 11100 KB Output is correct
13 Correct 3 ms 10948 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 11260 KB Output is correct
18 Correct 2 ms 11100 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 3 ms 10844 KB Output is correct
23 Correct 3 ms 11100 KB Output is correct
24 Correct 2 ms 11100 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct
26 Correct 2 ms 10844 KB Output is correct
27 Correct 2 ms 10840 KB Output is correct
28 Correct 4 ms 11100 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 11100 KB Output is correct
12 Correct 2 ms 11100 KB Output is correct
13 Correct 3 ms 10948 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 11260 KB Output is correct
18 Correct 2 ms 11100 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 3 ms 10844 KB Output is correct
23 Correct 3 ms 11100 KB Output is correct
24 Correct 2 ms 11100 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct
26 Correct 2 ms 10844 KB Output is correct
27 Correct 2 ms 10840 KB Output is correct
28 Correct 4 ms 11100 KB Output is correct
29 Correct 111 ms 32888 KB Output is correct
30 Correct 98 ms 33472 KB Output is correct
31 Correct 111 ms 37880 KB Output is correct
32 Incorrect 207 ms 70836 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 2 ms 10584 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 11100 KB Output is correct
12 Correct 2 ms 11100 KB Output is correct
13 Correct 3 ms 10948 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 11260 KB Output is correct
18 Correct 2 ms 11100 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 3 ms 10844 KB Output is correct
23 Correct 3 ms 11100 KB Output is correct
24 Correct 2 ms 11100 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct
26 Correct 2 ms 10844 KB Output is correct
27 Correct 2 ms 10840 KB Output is correct
28 Correct 4 ms 11100 KB Output is correct
29 Correct 2 ms 10840 KB Output is correct
30 Correct 3 ms 11096 KB Output is correct
31 Correct 2 ms 11096 KB Output is correct
32 Correct 2 ms 10840 KB Output is correct
33 Incorrect 3 ms 10844 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 85380 KB Output is correct
2 Correct 175 ms 54972 KB Output is correct
3 Correct 115 ms 37412 KB Output is correct
4 Correct 155 ms 49696 KB Output is correct
5 Correct 142 ms 62336 KB Output is correct
6 Incorrect 118 ms 44244 KB Output isn't correct
7 Halted 0 ms 0 KB -