oj.uz

Submission #998053

# Submission time Handle Problem Language Result Execution time Memory
998053 2024-06-13T08:54:00 Z salmon Jobs (BOI24_jobs) C++14
14 / 100
 306 ms 85112 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;

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\n",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({0,lst[i]});
    }
    else{
        sat = v[ii.second].first;
        offset = v[ii.second].second;
        if(lst[i] > 0) sat -> insert({- 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 -= 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,0};

        other = balls;
    }





    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});

    return {sat,offset};
}

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){
        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;
            //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::pair<std::set<std::pair<long long int, long long int> >*, long long int> dfs(int)':
Main.cpp:41: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]
   41 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
Main.cpp:27:19: warning: unused variable 'va' [-Wunused-variable]
   27 |     long long int va = lst[i];
      |                   ^~
Main.cpp: In function 'int main()':
Main.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf(" %d",&N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     scanf(" %lld",&money);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   scanf(" %d",&h);
      |   ~~~~~^~~~~~~~~~
Main.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf(" %d",&h1);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 85112 KB Output is correct
2 Correct 215 ms 53972 KB Output is correct
3 Correct 154 ms 37572 KB Output is correct
4 Correct 191 ms 51148 KB Output is correct
5 Correct 211 ms 65084 KB Output is correct
6 Incorrect 168 ms 44248 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 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 4 ms 11100 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 3 ms 10968 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 2 ms 11100 KB Output is correct
13 Correct 4 ms 10844 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 3 ms 10844 KB Output is correct
17 Correct 4 ms 11100 KB Output is correct
18 Correct 3 ms 11100 KB Output is correct
19 Correct 3 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 2 ms 10844 KB Output is correct
23 Correct 3 ms 11100 KB Output is correct
24 Correct 3 ms 11100 KB Output is correct
25 Correct 3 ms 10844 KB Output is correct
26 Correct 2 ms 10844 KB Output is correct
27 Correct 2 ms 10844 KB Output is correct
28 Correct 2 ms 11120 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 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 4 ms 11100 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 3 ms 10968 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 2 ms 11100 KB Output is correct
13 Correct 4 ms 10844 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 3 ms 10844 KB Output is correct
17 Correct 4 ms 11100 KB Output is correct
18 Correct 3 ms 11100 KB Output is correct
19 Correct 3 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 2 ms 10844 KB Output is correct
23 Correct 3 ms 11100 KB Output is correct
24 Correct 3 ms 11100 KB Output is correct
25 Correct 3 ms 10844 KB Output is correct
26 Correct 2 ms 10844 KB Output is correct
27 Correct 2 ms 10844 KB Output is correct
28 Correct 2 ms 11120 KB Output is correct
29 Correct 117 ms 32708 KB Output is correct
30 Correct 110 ms 33992 KB Output is correct
31 Correct 98 ms 37924 KB Output is correct
32 Incorrect 233 ms 75516 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 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 4 ms 11100 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 3 ms 10968 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 3 ms 11100 KB Output is correct
12 Correct 2 ms 11100 KB Output is correct
13 Correct 4 ms 10844 KB Output is correct
14 Correct 3 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 3 ms 10844 KB Output is correct
17 Correct 4 ms 11100 KB Output is correct
18 Correct 3 ms 11100 KB Output is correct
19 Correct 3 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 2 ms 10844 KB Output is correct
23 Correct 3 ms 11100 KB Output is correct
24 Correct 3 ms 11100 KB Output is correct
25 Correct 3 ms 10844 KB Output is correct
26 Correct 2 ms 10844 KB Output is correct
27 Correct 2 ms 10844 KB Output is correct
28 Correct 2 ms 11120 KB Output is correct
29 Correct 2 ms 10588 KB Output is correct
30 Correct 3 ms 11096 KB Output is correct
31 Correct 3 ms 11100 KB Output is correct
32 Correct 2 ms 10844 KB Output is correct
33 Incorrect 2 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 306 ms 85112 KB Output is correct
2 Correct 215 ms 53972 KB Output is correct
3 Correct 154 ms 37572 KB Output is correct
4 Correct 191 ms 51148 KB Output is correct
5 Correct 211 ms 65084 KB Output is correct
6 Incorrect 168 ms 44248 KB Output isn't correct
7 Halted 0 ms 0 KB -