답안 #841978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841978	2023-09-02T09:37:41 Z	browntoad	Magic Tree (CEOI19_magictree)	C++14	100 / 100	96 ms	32852 KB

magictree

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i, n) for (int i=(n); i>=1; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pip pair<int, pii>
#define ppi pair<pii, int>
#define ppp pair<pii, pii>
#define pdd pair<double ,double>
#define pcc pair<char, char>
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif

const ll inf = 1ll<<60;
const ll iinf = 2147483647;
const ll mod = 998244353;
const ll maxn=1e5+5;
const double PI=acos(-1);

ll pw(ll x, ll p, ll m=mod){
    ll ret=1;
    while (p>0){
        if (p&1){
            ret*=x;
            ret%=m;
        }
        x*=x;
        x%=m;
        p>>=1;
    }
    return ret;
}

ll inv(ll a, ll m=mod){
    return pw(a,m-2,m);
}
int n, m, k;
multiset<pii> dp[maxn];
vector<int> graph[maxn];
vector<pii> froot(maxn); // first is time, second is weight
void dfs(int x){
    pii lg = {0, -1};
    REP(i, SZ(graph[x])){
        dfs(graph[x][i]);
        if (SZ(dp[graph[x][i]]) > lg.f) {
            lg.f = SZ(dp[graph[x][i]]);
            lg.s = i;
        }
    }
    if (lg.s != -1) dp[x].swap(dp[graph[x][lg.s]]);
    REP(i, SZ(graph[x])){
        if (i == lg.s) continue;
        while(dp[graph[x][i]].size()){
            dp[x].insert(*(dp[graph[x][i]].begin()));
            dp[graph[x][i]].erase(dp[graph[x][i]].begin());
        }
    }
    if (froot[x].f == 0) return;
    if (SZ(dp[x])){
        auto it = dp[x].upper_bound({froot[x].f+1, 0});
        int cur = -(froot[x].s);
        while(it != dp[x].end()){
            cur += (*it).s;
            if (cur > 0){
                dp[x].insert({(*it).f, cur});
                dp[x].erase(it);
                break;
            }
            it = dp[x].erase(it);
        }
    }
    dp[x].insert(froot[x]);
}
signed main(){
    IOS();
    cin>>n>>m>>k;
    FOR(i, 2, n+1){
        int p; cin>>p;
        graph[p].pb(i);
    }
    REP(i, m){
        int x; cin>>x;
        cin>>froot[x].f>>froot[x].s;
    }
    dfs(1);
    int ans = 0;
    while(dp[1].size()){
        ans += (*(dp[1].begin())).s;
        dp[1].erase(dp[1].begin());
    }
    cout<<ans<<endl;
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	9048 KB	Output is correct
2	Correct	2 ms	9052 KB	Output is correct
3	Correct	2 ms	9052 KB	Output is correct
4	Correct	2 ms	9052 KB	Output is correct
5	Correct	3 ms	9052 KB	Output is correct
6	Correct	2 ms	9052 KB	Output is correct
7	Correct	2 ms	9052 KB	Output is correct
8	Correct	2 ms	9052 KB	Output is correct
9	Correct	2 ms	9052 KB	Output is correct

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	12112 KB	Output is correct
2	Correct	31 ms	17840 KB	Output is correct
3	Correct	86 ms	15696 KB	Output is correct
4	Correct	47 ms	15316 KB	Output is correct
5	Correct	68 ms	17232 KB	Output is correct

Subtask #3
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	9048 KB	Output is correct
2	Correct	2 ms	9052 KB	Output is correct
3	Correct	3 ms	9052 KB	Output is correct
4	Correct	42 ms	26460 KB	Output is correct
5	Correct	63 ms	32852 KB	Output is correct
6	Correct	55 ms	26660 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	82 ms	15260 KB	Output is correct
2	Correct	96 ms	18536 KB	Output is correct
3	Correct	64 ms	21872 KB	Output is correct
4	Correct	47 ms	17168 KB	Output is correct
5	Correct	67 ms	29508 KB	Output is correct

Subtask #5
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	9048 KB	Output is correct
2	Correct	2 ms	9052 KB	Output is correct
3	Correct	2 ms	9052 KB	Output is correct
4	Correct	2 ms	9052 KB	Output is correct
5	Correct	3 ms	9052 KB	Output is correct
6	Correct	2 ms	9052 KB	Output is correct
7	Correct	2 ms	9052 KB	Output is correct
8	Correct	2 ms	9052 KB	Output is correct
9	Correct	2 ms	9052 KB	Output is correct
10	Correct	67 ms	16292 KB	Output is correct
11	Correct	67 ms	16184 KB	Output is correct
12	Correct	59 ms	19300 KB	Output is correct
13	Correct	38 ms	16592 KB	Output is correct
14	Correct	54 ms	26452 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	9304 KB	Output is correct
2	Correct	17 ms	10844 KB	Output is correct
3	Correct	18 ms	10840 KB	Output is correct
4	Correct	16 ms	10840 KB	Output is correct
5	Correct	7 ms	10204 KB	Output is correct
6	Correct	17 ms	13148 KB	Output is correct
7	Correct	18 ms	16476 KB	Output is correct

Subtask #7
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	9048 KB	Output is correct
2	Correct	2 ms	9052 KB	Output is correct
3	Correct	2 ms	9052 KB	Output is correct
4	Correct	2 ms	9052 KB	Output is correct
5	Correct	3 ms	9052 KB	Output is correct
6	Correct	2 ms	9052 KB	Output is correct
7	Correct	2 ms	9052 KB	Output is correct
8	Correct	2 ms	9052 KB	Output is correct
9	Correct	2 ms	9052 KB	Output is correct
10	Correct	3 ms	9048 KB	Output is correct
11	Correct	2 ms	9052 KB	Output is correct
12	Correct	3 ms	9052 KB	Output is correct
13	Correct	42 ms	26460 KB	Output is correct
14	Correct	63 ms	32852 KB	Output is correct
15	Correct	55 ms	26660 KB	Output is correct
16	Correct	67 ms	16292 KB	Output is correct
17	Correct	67 ms	16184 KB	Output is correct
18	Correct	59 ms	19300 KB	Output is correct
19	Correct	38 ms	16592 KB	Output is correct
20	Correct	54 ms	26452 KB	Output is correct
21	Correct	14 ms	10332 KB	Output is correct
22	Correct	47 ms	14164 KB	Output is correct
23	Correct	47 ms	14164 KB	Output is correct
24	Correct	74 ms	16388 KB	Output is correct
25	Correct	47 ms	16900 KB	Output is correct
26	Correct	69 ms	18160 KB	Output is correct
27	Correct	58 ms	19412 KB	Output is correct

Subtask #8
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	9048 KB	Output is correct
2	Correct	2 ms	9052 KB	Output is correct
3	Correct	2 ms	9052 KB	Output is correct
4	Correct	2 ms	9052 KB	Output is correct
5	Correct	3 ms	9052 KB	Output is correct
6	Correct	2 ms	9052 KB	Output is correct
7	Correct	2 ms	9052 KB	Output is correct
8	Correct	2 ms	9052 KB	Output is correct
9	Correct	2 ms	9052 KB	Output is correct
10	Correct	35 ms	12112 KB	Output is correct
11	Correct	31 ms	17840 KB	Output is correct
12	Correct	86 ms	15696 KB	Output is correct
13	Correct	47 ms	15316 KB	Output is correct
14	Correct	68 ms	17232 KB	Output is correct
15	Correct	3 ms	9048 KB	Output is correct
16	Correct	2 ms	9052 KB	Output is correct
17	Correct	3 ms	9052 KB	Output is correct
18	Correct	42 ms	26460 KB	Output is correct
19	Correct	63 ms	32852 KB	Output is correct
20	Correct	55 ms	26660 KB	Output is correct
21	Correct	82 ms	15260 KB	Output is correct
22	Correct	96 ms	18536 KB	Output is correct
23	Correct	64 ms	21872 KB	Output is correct
24	Correct	47 ms	17168 KB	Output is correct
25	Correct	67 ms	29508 KB	Output is correct
26	Correct	67 ms	16292 KB	Output is correct
27	Correct	67 ms	16184 KB	Output is correct
28	Correct	59 ms	19300 KB	Output is correct
29	Correct	38 ms	16592 KB	Output is correct
30	Correct	54 ms	26452 KB	Output is correct
31	Correct	5 ms	9304 KB	Output is correct
32	Correct	17 ms	10844 KB	Output is correct
33	Correct	18 ms	10840 KB	Output is correct
34	Correct	16 ms	10840 KB	Output is correct
35	Correct	7 ms	10204 KB	Output is correct
36	Correct	17 ms	13148 KB	Output is correct
37	Correct	18 ms	16476 KB	Output is correct
38	Correct	14 ms	10332 KB	Output is correct
39	Correct	47 ms	14164 KB	Output is correct
40	Correct	47 ms	14164 KB	Output is correct
41	Correct	74 ms	16388 KB	Output is correct
42	Correct	47 ms	16900 KB	Output is correct
43	Correct	69 ms	18160 KB	Output is correct
44	Correct	58 ms	19412 KB	Output is correct
45	Correct	16 ms	10588 KB	Output is correct
46	Correct	50 ms	14676 KB	Output is correct
47	Correct	49 ms	14932 KB	Output is correct
48	Correct	83 ms	17748 KB	Output is correct
49	Correct	50 ms	17360 KB	Output is correct
50	Correct	73 ms	19220 KB	Output is correct
51	Correct	66 ms	20308 KB	Output is correct

답안 #841978

Compilation message