답안 #419491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419491	2021-06-07T07:49:23 Z	2548631	Magic Tree (CEOI19_magictree)	C++17	100 / 100	195 ms	41520 KB

magictree

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef complex<ld> cp;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<cp> vcp;
typedef vector<ld> vld;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;

#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define forw(i,l,r) for( int i = (l) ; i < (r) ; i++ )
#define forb(i,r,l) for( int i = (r) ; i >= (l) ; i-- )
#define log2i(x) (32 - __builtin_clz((x)) - 1)
#define log2ll(x) (64 - __builtin_clzll((x)) - 1)
#define Pi 3.141592653589793
#define sz(x) (int)x.size()
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

const int N = 1e5+7;
int n,m,k;
int p[N],pos[N];
ii a[N];
map<int,ll> q[N];

int add(int x, int y) {
    if(sz(q[x])<sz(q[y])) swap(x,y);
    for(auto tmp:q[y]) q[x][tmp.fi]+=tmp.se;
    return x;
}

int main() {
    fastIO;
#ifndef ONLINE_JUDGE
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
#endif // ONLINE_JUDGE

    cin >> n >> m >> k;
    forw(i,1,n) cin >> p[i], p[i]--;
    forw(i,0,m) {
        int u,d,w; cin >> u >> d >> w;
        u--;
        a[u]=mp(d,w);
    }
    iota(pos,pos+n,0);
    forb(i,n-1,1) {
        q[pos[i]][a[i].fi]+=a[i].se;
        int tmp=a[i].se;
        while(true) {
            auto it=q[pos[i]].upper_bound(a[i].fi);
            if(it==q[pos[i]].end()) break;
            if(tmp>=it->se) {
                tmp-=it->se;
                q[pos[i]].erase(it);
            } else {it->se-=tmp; break;}
        }
        pos[p[i]]=add(pos[p[i]],pos[i]);
    }
    ll ans=0;
    for(auto x:q[pos[0]]) ans+=x.se;
    cout << ans;
    return 0;
}

Subtask #1
6.0 / 6.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	4940 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	4 ms	5020 KB	Output is correct
6	Correct	4 ms	4940 KB	Output is correct
7	Correct	3 ms	4940 KB	Output is correct
8	Correct	3 ms	4912 KB	Output is correct
9	Correct	3 ms	4972 KB	Output is correct

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	81 ms	20944 KB	Output is correct
2	Correct	40 ms	10172 KB	Output is correct
3	Correct	195 ms	41520 KB	Output is correct
4	Correct	109 ms	19416 KB	Output is correct
5	Correct	150 ms	24004 KB	Output is correct

Subtask #3
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	4940 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Correct	3 ms	5068 KB	Output is correct
4	Correct	55 ms	9276 KB	Output is correct
5	Correct	73 ms	13224 KB	Output is correct
6	Correct	68 ms	9304 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	79 ms	14020 KB	Output is correct
2	Correct	68 ms	12928 KB	Output is correct
3	Correct	54 ms	10788 KB	Output is correct
4	Correct	53 ms	15268 KB	Output is correct
5	Correct	45 ms	9416 KB	Output is correct

Subtask #5
16.0 / 16.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	4940 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	4 ms	5020 KB	Output is correct
6	Correct	4 ms	4940 KB	Output is correct
7	Correct	3 ms	4940 KB	Output is correct
8	Correct	3 ms	4912 KB	Output is correct
9	Correct	3 ms	4972 KB	Output is correct
10	Correct	93 ms	17188 KB	Output is correct
11	Correct	89 ms	15916 KB	Output is correct
12	Correct	52 ms	10316 KB	Output is correct
13	Correct	52 ms	14712 KB	Output is correct
14	Correct	43 ms	8744 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	6348 KB	Output is correct
2	Correct	34 ms	10996 KB	Output is correct
3	Correct	36 ms	10984 KB	Output is correct
4	Correct	41 ms	11132 KB	Output is correct
5	Correct	23 ms	13636 KB	Output is correct
6	Correct	32 ms	11636 KB	Output is correct
7	Correct	24 ms	8972 KB	Output is correct

Subtask #7
22.0 / 22.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	4940 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	4 ms	5020 KB	Output is correct
6	Correct	4 ms	4940 KB	Output is correct
7	Correct	3 ms	4940 KB	Output is correct
8	Correct	3 ms	4912 KB	Output is correct
9	Correct	3 ms	4972 KB	Output is correct
10	Correct	4 ms	4940 KB	Output is correct
11	Correct	4 ms	4940 KB	Output is correct
12	Correct	3 ms	5068 KB	Output is correct
13	Correct	55 ms	9276 KB	Output is correct
14	Correct	73 ms	13224 KB	Output is correct
15	Correct	68 ms	9304 KB	Output is correct
16	Correct	93 ms	17188 KB	Output is correct
17	Correct	89 ms	15916 KB	Output is correct
18	Correct	52 ms	10316 KB	Output is correct
19	Correct	52 ms	14712 KB	Output is correct
20	Correct	43 ms	8744 KB	Output is correct
21	Correct	26 ms	9128 KB	Output is correct
22	Correct	93 ms	20380 KB	Output is correct
23	Correct	108 ms	24236 KB	Output is correct
24	Correct	157 ms	33112 KB	Output is correct
25	Correct	95 ms	18764 KB	Output is correct
26	Correct	124 ms	18976 KB	Output is correct
27	Correct	88 ms	12100 KB	Output is correct

Subtask #8
17.0 / 17.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	4940 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	4 ms	5020 KB	Output is correct
6	Correct	4 ms	4940 KB	Output is correct
7	Correct	3 ms	4940 KB	Output is correct
8	Correct	3 ms	4912 KB	Output is correct
9	Correct	3 ms	4972 KB	Output is correct
10	Correct	81 ms	20944 KB	Output is correct
11	Correct	40 ms	10172 KB	Output is correct
12	Correct	195 ms	41520 KB	Output is correct
13	Correct	109 ms	19416 KB	Output is correct
14	Correct	150 ms	24004 KB	Output is correct
15	Correct	4 ms	4940 KB	Output is correct
16	Correct	4 ms	4940 KB	Output is correct
17	Correct	3 ms	5068 KB	Output is correct
18	Correct	55 ms	9276 KB	Output is correct
19	Correct	73 ms	13224 KB	Output is correct
20	Correct	68 ms	9304 KB	Output is correct
21	Correct	79 ms	14020 KB	Output is correct
22	Correct	68 ms	12928 KB	Output is correct
23	Correct	54 ms	10788 KB	Output is correct
24	Correct	53 ms	15268 KB	Output is correct
25	Correct	45 ms	9416 KB	Output is correct
26	Correct	93 ms	17188 KB	Output is correct
27	Correct	89 ms	15916 KB	Output is correct
28	Correct	52 ms	10316 KB	Output is correct
29	Correct	52 ms	14712 KB	Output is correct
30	Correct	43 ms	8744 KB	Output is correct
31	Correct	10 ms	6348 KB	Output is correct
32	Correct	34 ms	10996 KB	Output is correct
33	Correct	36 ms	10984 KB	Output is correct
34	Correct	41 ms	11132 KB	Output is correct
35	Correct	23 ms	13636 KB	Output is correct
36	Correct	32 ms	11636 KB	Output is correct
37	Correct	24 ms	8972 KB	Output is correct
38	Correct	26 ms	9128 KB	Output is correct
39	Correct	93 ms	20380 KB	Output is correct
40	Correct	108 ms	24236 KB	Output is correct
41	Correct	157 ms	33112 KB	Output is correct
42	Correct	95 ms	18764 KB	Output is correct
43	Correct	124 ms	18976 KB	Output is correct
44	Correct	88 ms	12100 KB	Output is correct
45	Correct	26 ms	9668 KB	Output is correct
46	Correct	101 ms	21672 KB	Output is correct
47	Correct	117 ms	25804 KB	Output is correct
48	Correct	184 ms	36488 KB	Output is correct
49	Correct	105 ms	19368 KB	Output is correct
50	Correct	135 ms	20004 KB	Output is correct
51	Correct	91 ms	12996 KB	Output is correct

답안 #419491

Compilation message