답안 #1110996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1110996	2024-11-11T09:09:38 Z	crafticat	Magic Tree (CEOI19_magictree)	C++17	100 / 100	137 ms	47776 KB

magictree

#include <bits/stdc++.h>

using namespace std;

template<typename T>
using V = vector<T>;
using ll = long long;
using vi = V<ll>;
using vb = V<bool>;

using pi = pair<ll,ll>;
#define F0R(i,n) for (ll i = 0; i < n;i++)
#define FOR(i, j, n) for(ll i = j; i < n;i++)
#define ckmin(x,y) x = min(x,y)
#define f first
#define s second
constexpr ll INF = 1e18 + 5;

struct STL {
    vi pollers;
    V<multiset<pi>> gradients;

    STL(ll n) {
        pollers.resize(n);
        gradients.resize(n);
        for (ll i = 0; i < n;i++) {
            pollers[i] = i;
        }
    }

    void merge(ll x, ll y) {
        ll pX = pollers[x], pY = pollers[y];
        if (gradients[pY].size() > gradients[pX].size()) swap(pX,pY);

        pollers[y] = pX;
        pollers[x] = pX;

        for (auto elm : gradients[pY]) {
            gradients[pX].insert(elm);
        }
    }

    void insert(ll x, ll t, ll v) {
        x = pollers[x];

        ll sum = 0;
        while (true) {
            auto it = gradients[x].upper_bound({t, INF});
            if (it == gradients[x].end()) break;

            ll t1 = it->first;
            sum += it->second;
            gradients[x].erase(it);

            if (sum > v) {
                sum -= v;
                gradients[x].insert({t1, sum});
                break;
            }
        }

        gradients[x].insert({t,v});
    }
    ll query(ll x) {
        x = pollers[x];

        ll sum = 0;
        for (auto [v,y] : gradients[x]) {
            sum += y;
        }
        return sum;
    }
};

V<pi> dat;
V<vi> g;
STL *stl;

void solve(ll x, ll p) {
    for (auto y : g[x]) {
        if (y == p) continue;
        solve(y, x);
        stl->merge(x, y);
    }
    stl->insert(x, dat[x].f, dat[x].s);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    ll n, m, k; cin >> n >> m >> k;
    g.resize(n + 1);
    stl = new STL(n + 1);

    FOR(i, 2, n + 1) {
        ll p; cin >> p;
        g[p].push_back(i);
        g[i].push_back(p);
    }

    dat.resize(n + 1);
    F0R(i, m) {
        ll v, t, p; cin >> v >> t >> p;
        dat[v] = {t, p};
    }

    solve(1, -1);
    cout << stl->query(1);

    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	109 ms	45908 KB	Output is correct
2	Correct	76 ms	31560 KB	Output is correct
3	Correct	113 ms	47176 KB	Output is correct
4	Correct	73 ms	28348 KB	Output is correct
5	Correct	94 ms	30152 KB	Output is correct

Subtask #3
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	592 KB	Output is correct
2	Correct	1 ms	592 KB	Output is correct
3	Correct	2 ms	592 KB	Output is correct
4	Correct	58 ms	30024 KB	Output is correct
5	Correct	74 ms	36424 KB	Output is correct
6	Correct	77 ms	30024 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	136 ms	40520 KB	Output is correct
2	Correct	137 ms	47776 KB	Output is correct
3	Correct	79 ms	29132 KB	Output is correct
4	Correct	68 ms	27836 KB	Output is correct
5	Correct	72 ms	35664 KB	Output is correct

Subtask #5
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	102 ms	37192 KB	Output is correct
11	Correct	93 ms	37960 KB	Output is correct
12	Correct	69 ms	24252 KB	Output is correct
13	Correct	58 ms	26060 KB	Output is correct
14	Correct	73 ms	31048 KB	Output is correct

Subtask #6
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	8784 KB	Output is correct
2	Correct	100 ms	46380 KB	Output is correct
3	Correct	86 ms	45640 KB	Output is correct
4	Correct	84 ms	44880 KB	Output is correct
5	Correct	33 ms	26308 KB	Output is correct
6	Correct	82 ms	30796 KB	Output is correct
7	Correct	65 ms	31284 KB	Output is correct

Subtask #7
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	2 ms	592 KB	Output is correct
11	Correct	1 ms	592 KB	Output is correct
12	Correct	2 ms	592 KB	Output is correct
13	Correct	58 ms	30024 KB	Output is correct
14	Correct	74 ms	36424 KB	Output is correct
15	Correct	77 ms	30024 KB	Output is correct
16	Correct	102 ms	37192 KB	Output is correct
17	Correct	93 ms	37960 KB	Output is correct
18	Correct	69 ms	24252 KB	Output is correct
19	Correct	58 ms	26060 KB	Output is correct
20	Correct	73 ms	31048 KB	Output is correct
21	Correct	17 ms	6992 KB	Output is correct
22	Correct	117 ms	42452 KB	Output is correct
23	Correct	106 ms	42324 KB	Output is correct
24	Correct	118 ms	36740 KB	Output is correct
25	Correct	79 ms	26044 KB	Output is correct
26	Correct	85 ms	26708 KB	Output is correct
27	Correct	76 ms	24008 KB	Output is correct

Subtask #8
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	109 ms	45908 KB	Output is correct
11	Correct	76 ms	31560 KB	Output is correct
12	Correct	113 ms	47176 KB	Output is correct
13	Correct	73 ms	28348 KB	Output is correct
14	Correct	94 ms	30152 KB	Output is correct
15	Correct	2 ms	592 KB	Output is correct
16	Correct	1 ms	592 KB	Output is correct
17	Correct	2 ms	592 KB	Output is correct
18	Correct	58 ms	30024 KB	Output is correct
19	Correct	74 ms	36424 KB	Output is correct
20	Correct	77 ms	30024 KB	Output is correct
21	Correct	136 ms	40520 KB	Output is correct
22	Correct	137 ms	47776 KB	Output is correct
23	Correct	79 ms	29132 KB	Output is correct
24	Correct	68 ms	27836 KB	Output is correct
25	Correct	72 ms	35664 KB	Output is correct
26	Correct	102 ms	37192 KB	Output is correct
27	Correct	93 ms	37960 KB	Output is correct
28	Correct	69 ms	24252 KB	Output is correct
29	Correct	58 ms	26060 KB	Output is correct
30	Correct	73 ms	31048 KB	Output is correct
31	Correct	15 ms	8784 KB	Output is correct
32	Correct	100 ms	46380 KB	Output is correct
33	Correct	86 ms	45640 KB	Output is correct
34	Correct	84 ms	44880 KB	Output is correct
35	Correct	33 ms	26308 KB	Output is correct
36	Correct	82 ms	30796 KB	Output is correct
37	Correct	65 ms	31284 KB	Output is correct
38	Correct	17 ms	6992 KB	Output is correct
39	Correct	117 ms	42452 KB	Output is correct
40	Correct	106 ms	42324 KB	Output is correct
41	Correct	118 ms	36740 KB	Output is correct
42	Correct	79 ms	26044 KB	Output is correct
43	Correct	85 ms	26708 KB	Output is correct
44	Correct	76 ms	24008 KB	Output is correct
45	Correct	25 ms	7908 KB	Output is correct
46	Correct	99 ms	45380 KB	Output is correct
47	Correct	100 ms	44612 KB	Output is correct
48	Correct	108 ms	41964 KB	Output is correct
49	Correct	73 ms	28348 KB	Output is correct
50	Correct	96 ms	29512 KB	Output is correct
51	Correct	79 ms	26708 KB	Output is correct

답안 #1110996

Compilation message