oj.uz

답안 #417033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
417033 2021-06-03T10:48:46 Z tqbfjotld Worst Reporter 4 (JOI21_worst_reporter4) C++14
79 / 100
 373 ms 62824 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int h[200005];
int c[200005];
vector<int> adjl[200005];

///pos, increase
set<pair<int,int> > func(int node){
    set<pair<int,int> > res1;
    for (auto x : adjl[node]){
        auto res = func(x);
        if (res.size()>res1.size()) swap(res,res1);
        for (auto y : res){
            auto it = res1.lower_bound({y.first,-1});
            if (it!=res1.end() && (*it).first==y.first){
                int t = (*it).second;
                res1.erase(it);
                res1.insert({y.first,y.second+t});
            }
            else{
                res1.insert({y.first,y.second});
            }
        }
    }
    pair<int,int> to_insert = {h[node]+1,c[node]};
    int cursum = 0;
    auto it = res1.lower_bound({h[node]+1,-1});
    if (it!=res1.end() && (*it).first==to_insert.first){
        int t = (*it).second;
        res1.erase(it);
        res1.insert({to_insert.first,to_insert.second+t});
    }
    else{
        res1.insert(to_insert);
    }
    it = res1.lower_bound(to_insert);
    bool done = false;
    while (it!=res1.begin()){
        it--;
        cursum += (*it).second;
        int curpos = (*it).first;
        it = res1.erase(it);
        if (cursum >= c[node]){
            int rem = cursum-c[node];
            if (rem!=0){
                res1.insert({curpos,rem});
            }
            done = true;
            break;
        }
    }
    if (!done){
        if (cursum!=0){
            if ((!res1.empty()) && (*res1.begin()).first==0){
                cursum += (*res1.begin()).second;
                res1.erase(res1.begin());
                res1.insert({0,cursum});
            }
            else
                res1.insert({0,cursum});
        }
    }
    else{
        if ((!res1.empty()) && (*res1.begin()).first==0){
            int t = (*res1.begin()).second;
            res1.erase(res1.begin());
            res1.insert({0,c[node]+t});
        }
        else
            res1.insert({0,c[node]});
    }
    /*printf("node %lld, ret ",node);
    for (auto x : res1){
        printf("(%lld,%lld) ",x);
    }
    printf("\n");*/
    return res1;
}

main(){
    int n;
    scanf("%lld",&n);
    for (int x = 1; x<=n; x++){
        int t;
        scanf("%lld%lld%lld",&t,&h[x],&c[x]);
        if (x!=1){
            adjl[t].push_back(x);
        }
    }
    auto res = func(1);
    if (res.empty()){
        printf("0");
    }
    else if ((*res.begin()).first!=0){
        printf("0");
    }
    else{
        printf("%lld",(*res.begin()).second);
    }
}

Compilation message

worst_reporter2.cpp:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   82 | main(){
      | ^~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
worst_reporter2.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         scanf("%lld%lld%lld",&t,&h[x],&c[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 9 ms 5516 KB Output is correct
6 Correct 8 ms 5196 KB Output is correct
7 Correct 7 ms 5196 KB Output is correct
8 Correct 9 ms 5452 KB Output is correct
9 Correct 9 ms 5268 KB Output is correct
10 Correct 7 ms 5196 KB Output is correct
11 Correct 6 ms 5196 KB Output is correct
12 Correct 8 ms 6348 KB Output is correct
13 Correct 7 ms 6348 KB Output is correct
14 Correct 8 ms 5836 KB Output is correct
15 Correct 8 ms 5836 KB Output is correct
16 Correct 10 ms 5580 KB Output is correct
17 Correct 8 ms 5196 KB Output is correct
18 Correct 6 ms 5196 KB Output is correct
19 Correct 8 ms 5964 KB Output is correct
20 Correct 7 ms 5708 KB Output is correct
21 Correct 6 ms 5708 KB Output is correct
22 Correct 7 ms 5524 KB Output is correct
23 Correct 6 ms 5196 KB Output is correct
24 Correct 8 ms 5964 KB Output is correct
25 Correct 7 ms 5836 KB Output is correct
26 Correct 6 ms 6348 KB Output is correct
27 Correct 7 ms 5836 KB Output is correct
28 Correct 8 ms 6052 KB Output is correct
29 Correct 8 ms 6292 KB Output is correct
30 Correct 9 ms 6296 KB Output is correct
31 Correct 8 ms 6220 KB Output is correct

Subtask #2
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 9 ms 5516 KB Output is correct
6 Correct 8 ms 5196 KB Output is correct
7 Correct 7 ms 5196 KB Output is correct
8 Correct 9 ms 5452 KB Output is correct
9 Correct 9 ms 5268 KB Output is correct
10 Correct 7 ms 5196 KB Output is correct
11 Correct 6 ms 5196 KB Output is correct
12 Correct 8 ms 6348 KB Output is correct
13 Correct 7 ms 6348 KB Output is correct
14 Correct 8 ms 5836 KB Output is correct
15 Correct 8 ms 5836 KB Output is correct
16 Correct 10 ms 5580 KB Output is correct
17 Correct 8 ms 5196 KB Output is correct
18 Correct 6 ms 5196 KB Output is correct
19 Correct 8 ms 5964 KB Output is correct
20 Correct 7 ms 5708 KB Output is correct
21 Correct 6 ms 5708 KB Output is correct
22 Correct 7 ms 5524 KB Output is correct
23 Correct 6 ms 5196 KB Output is correct
24 Correct 8 ms 5964 KB Output is correct
25 Correct 7 ms 5836 KB Output is correct
26 Correct 6 ms 6348 KB Output is correct
27 Correct 7 ms 5836 KB Output is correct
28 Correct 8 ms 6052 KB Output is correct
29 Correct 8 ms 6292 KB Output is correct
30 Correct 9 ms 6296 KB Output is correct
31 Correct 8 ms 6220 KB Output is correct
32 Correct 9 ms 5452 KB Output is correct
33 Correct 373 ms 29184 KB Output is correct
34 Correct 275 ms 17296 KB Output is correct
35 Correct 350 ms 27080 KB Output is correct
36 Correct 263 ms 17288 KB Output is correct
37 Correct 174 ms 16848 KB Output is correct
38 Correct 147 ms 16764 KB Output is correct
39 Correct 217 ms 60256 KB Output is correct
40 Correct 217 ms 60228 KB Output is correct
41 Correct 154 ms 60192 KB Output is correct
42 Correct 210 ms 40004 KB Output is correct
43 Correct 205 ms 39800 KB Output is correct
44 Correct 365 ms 28480 KB Output is correct
45 Correct 263 ms 16616 KB Output is correct
46 Correct 102 ms 16268 KB Output is correct
47 Correct 253 ms 43600 KB Output is correct
48 Correct 180 ms 36700 KB Output is correct
49 Correct 133 ms 36544 KB Output is correct
50 Correct 201 ms 26396 KB Output is correct
51 Correct 125 ms 14000 KB Output is correct
52 Correct 259 ms 44608 KB Output is correct
53 Correct 171 ms 37556 KB Output is correct
54 Correct 138 ms 60356 KB Output is correct
55 Correct 217 ms 45844 KB Output is correct
56 Correct 233 ms 57412 KB Output is correct
57 Correct 228 ms 62824 KB Output is correct
58 Correct 287 ms 57892 KB Output is correct
59 Correct 280 ms 57896 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 9 ms 5516 KB Output is correct
6 Correct 8 ms 5196 KB Output is correct
7 Correct 7 ms 5196 KB Output is correct
8 Correct 9 ms 5452 KB Output is correct
9 Correct 9 ms 5268 KB Output is correct
10 Correct 7 ms 5196 KB Output is correct
11 Correct 6 ms 5196 KB Output is correct
12 Correct 8 ms 6348 KB Output is correct
13 Correct 7 ms 6348 KB Output is correct
14 Correct 8 ms 5836 KB Output is correct
15 Correct 8 ms 5836 KB Output is correct
16 Correct 10 ms 5580 KB Output is correct
17 Correct 8 ms 5196 KB Output is correct
18 Correct 6 ms 5196 KB Output is correct
19 Correct 8 ms 5964 KB Output is correct
20 Correct 7 ms 5708 KB Output is correct
21 Correct 6 ms 5708 KB Output is correct
22 Correct 7 ms 5524 KB Output is correct
23 Correct 6 ms 5196 KB Output is correct
24 Correct 8 ms 5964 KB Output is correct
25 Correct 7 ms 5836 KB Output is correct
26 Correct 6 ms 6348 KB Output is correct
27 Correct 7 ms 5836 KB Output is correct
28 Correct 8 ms 6052 KB Output is correct
29 Correct 8 ms 6292 KB Output is correct
30 Correct 9 ms 6296 KB Output is correct
31 Correct 8 ms 6220 KB Output is correct
32 Correct 9 ms 5452 KB Output is correct
33 Correct 373 ms 29184 KB Output is correct
34 Correct 275 ms 17296 KB Output is correct
35 Correct 350 ms 27080 KB Output is correct
36 Correct 263 ms 17288 KB Output is correct
37 Correct 174 ms 16848 KB Output is correct
38 Correct 147 ms 16764 KB Output is correct
39 Correct 217 ms 60256 KB Output is correct
40 Correct 217 ms 60228 KB Output is correct
41 Correct 154 ms 60192 KB Output is correct
42 Correct 210 ms 40004 KB Output is correct
43 Correct 205 ms 39800 KB Output is correct
44 Correct 365 ms 28480 KB Output is correct
45 Correct 263 ms 16616 KB Output is correct
46 Correct 102 ms 16268 KB Output is correct
47 Correct 253 ms 43600 KB Output is correct
48 Correct 180 ms 36700 KB Output is correct
49 Correct 133 ms 36544 KB Output is correct
50 Correct 201 ms 26396 KB Output is correct
51 Correct 125 ms 14000 KB Output is correct
52 Correct 259 ms 44608 KB Output is correct
53 Correct 171 ms 37556 KB Output is correct
54 Correct 138 ms 60356 KB Output is correct
55 Correct 217 ms 45844 KB Output is correct
56 Correct 233 ms 57412 KB Output is correct
57 Correct 228 ms 62824 KB Output is correct
58 Correct 287 ms 57892 KB Output is correct
59 Correct 280 ms 57896 KB Output is correct
60 Correct 3 ms 4940 KB Output is correct
61 Incorrect 3 ms 4988 KB Output isn't correct
62 Halted 0 ms 0 KB -