답안 #246296

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
246296	2020-07-08T15:09:24 Z	2fat2code	Magic Tree (CEOI19_magictree)	C++17	100 / 100	174 ms	38520 KB

magictree

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #246296

Compilation message