oj.uz

Submission #246296

# Submission time Handle Problem Language Result Execution time Memory
246296 2020-07-08T15:09:24 Z 2fat2code Magic Tree (CEOI19_magictree) C++17
100 / 100
 174 ms 38520 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sz() size()
#define fr first
#define sc second
#define int long long
#define mp make_pair
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;

const int nmax = 100005;

struct fruct{
    int prezent, day, juice;
    fruct(){prezent = -1;}
}a[nmax];

map<int,int>dp[nmax];
int n,m,k,dp_sub[nmax];
vector<int>nod[nmax];

void add(int indx, pair<int,int>val){
    dp[indx][val.fr] += val.sc;
}

void rationalize(int indx, pair<int,int>val){
    dp[indx][val.fr] += val.sc;
    auto it = dp[indx].upper_bound(val.fr);
    int curr = 0;
    while(it != dp[indx].end()){
        curr += (it->second);
        if(curr > val.sc) break;
        else{
            auto tz = it;
            ++it;
            dp[indx].erase(tz);
        }
    }
    if(it != dp[indx].end()){
        dp[indx][it->first] = (curr - val.sc);
    }
}

void DFS(int s){
    int heavy = -1, sz = 0;
    for(auto it : nod[s]){
        DFS(it);
        dp_sub[s] += dp_sub[it];
        if(sz < dp_sub[it]){
            sz = dp_sub[it];
            heavy = it;
        }
    }
    dp_sub[s] ++;
    if(heavy != -1){
        swap(dp[s],dp[heavy]);
    }
    for(auto it : nod[s]){
        if(it != heavy){
            for(auto curr : dp[it]){
                add(s,curr);
            }
        }
    }
    if(a[s].prezent == 1){
        rationalize(s,{a[s].day, a[s].juice});
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    srand(chrono::steady_clock::now().time_since_epoch().count());
    cin >> n >> m >> k;
    for(int i=2;i<=n;i++){
        int x;
        cin >> x;
        nod[x].push_back(i);
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin >> x >> y >> z;
        a[x].prezent = 1;
        a[x].day = y;
        a[x].juice = z;
    }
    DFS(1);
    int ans = 0;
    for(auto it : dp[1]){
        ans += (it.sc);
    }
    cout << ans << '\n';
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 14 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 21372 KB Output is correct
2 Correct 61 ms 22776 KB Output is correct
3 Correct 154 ms 38520 KB Output is correct
4 Correct 90 ms 22764 KB Output is correct
5 Correct 147 ms 24952 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9940 KB Output is correct
2 Correct 10 ms 9856 KB Output is correct
3 Correct 10 ms 9984 KB Output is correct
4 Correct 76 ms 29688 KB Output is correct
5 Correct 98 ms 33656 KB Output is correct
6 Correct 91 ms 29688 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 18296 KB Output is correct
2 Correct 91 ms 17424 KB Output is correct
3 Correct 89 ms 22008 KB Output is correct
4 Correct 54 ms 18800 KB Output is correct
5 Correct 78 ms 29944 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 14 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 105 ms 20344 KB Output is correct
11 Correct 95 ms 19448 KB Output is correct
12 Correct 70 ms 21368 KB Output is correct
13 Correct 51 ms 18028 KB Output is correct
14 Correct 65 ms 29304 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 10624 KB Output is correct
2 Correct 43 ms 13176 KB Output is correct
3 Correct 42 ms 13176 KB Output is correct
4 Correct 45 ms 13176 KB Output is correct
5 Correct 18 ms 11640 KB Output is correct
6 Correct 43 ms 15744 KB Output is correct
7 Correct 40 ms 19328 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 14 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 11 ms 9940 KB Output is correct
11 Correct 10 ms 9856 KB Output is correct
12 Correct 10 ms 9984 KB Output is correct
13 Correct 76 ms 29688 KB Output is correct
14 Correct 98 ms 33656 KB Output is correct
15 Correct 91 ms 29688 KB Output is correct
16 Correct 105 ms 20344 KB Output is correct
17 Correct 95 ms 19448 KB Output is correct
18 Correct 70 ms 21368 KB Output is correct
19 Correct 51 ms 18028 KB Output is correct
20 Correct 65 ms 29304 KB Output is correct
21 Correct 30 ms 13056 KB Output is correct
22 Correct 96 ms 21496 KB Output is correct
23 Correct 104 ms 24696 KB Output is correct
24 Correct 154 ms 32760 KB Output is correct
25 Correct 81 ms 22000 KB Output is correct
26 Correct 134 ms 24220 KB Output is correct
27 Correct 106 ms 23160 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 10 ms 9728 KB Output is correct
5 Correct 14 ms 9728 KB Output is correct
6 Correct 10 ms 9728 KB Output is correct
7 Correct 10 ms 9728 KB Output is correct
8 Correct 10 ms 9728 KB Output is correct
9 Correct 10 ms 9728 KB Output is correct
10 Correct 94 ms 21372 KB Output is correct
11 Correct 61 ms 22776 KB Output is correct
12 Correct 154 ms 38520 KB Output is correct
13 Correct 90 ms 22764 KB Output is correct
14 Correct 147 ms 24952 KB Output is correct
15 Correct 11 ms 9940 KB Output is correct
16 Correct 10 ms 9856 KB Output is correct
17 Correct 10 ms 9984 KB Output is correct
18 Correct 76 ms 29688 KB Output is correct
19 Correct 98 ms 33656 KB Output is correct
20 Correct 91 ms 29688 KB Output is correct
21 Correct 92 ms 18296 KB Output is correct
22 Correct 91 ms 17424 KB Output is correct
23 Correct 89 ms 22008 KB Output is correct
24 Correct 54 ms 18800 KB Output is correct
25 Correct 78 ms 29944 KB Output is correct
26 Correct 105 ms 20344 KB Output is correct
27 Correct 95 ms 19448 KB Output is correct
28 Correct 70 ms 21368 KB Output is correct
29 Correct 51 ms 18028 KB Output is correct
30 Correct 65 ms 29304 KB Output is correct
31 Correct 16 ms 10624 KB Output is correct
32 Correct 43 ms 13176 KB Output is correct
33 Correct 42 ms 13176 KB Output is correct
34 Correct 45 ms 13176 KB Output is correct
35 Correct 18 ms 11640 KB Output is correct
36 Correct 43 ms 15744 KB Output is correct
37 Correct 40 ms 19328 KB Output is correct
38 Correct 30 ms 13056 KB Output is correct
39 Correct 96 ms 21496 KB Output is correct
40 Correct 104 ms 24696 KB Output is correct
41 Correct 154 ms 32760 KB Output is correct
42 Correct 81 ms 22000 KB Output is correct
43 Correct 134 ms 24220 KB Output is correct
44 Correct 106 ms 23160 KB Output is correct
45 Correct 36 ms 13568 KB Output is correct
46 Correct 154 ms 22520 KB Output is correct
47 Correct 121 ms 25848 KB Output is correct
48 Correct 174 ms 35832 KB Output is correct
49 Correct 88 ms 22768 KB Output is correct
50 Correct 133 ms 25080 KB Output is correct
51 Correct 122 ms 24164 KB Output is correct