oj.uz

Submission #897030

# Submission time Handle Problem Language Result Execution time Memory
897030 2024-01-02T12:39:46 Z themm1 Magic Tree (CEOI19_magictree) C++17
100 / 100
 119 ms 38224 KB 
#include <bits/stdc++.h>
using namespace std;
// ordered set whith s.order_of_key(x) method, which returns rank of element x in set s
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

// pair printing
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << "; " << par.second << ")"; return out;}
// set printing
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// map printing
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// unordered_set printing
template <class T>
ostream& operator<<(ostream& out, const unordered_set<T> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// unordered_map printing
template <class T, class U>
ostream& operator<<(ostream& out, const unordered_map<T, U> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// vector printing
template<class T>
ostream& operator<<(ostream& out, const vector<T> &cont){ out << "[";  for (const auto &x:cont) out << x << ", ";  out << "]"; return out;}

#define print(x) cout << (x) << endl;
#define dmp(x) cerr << #x << " = " << x << endl
#define dmpn(x) cerr << #x << " = " << x << "; "
#define dmpl(x) cerr << "Line " << __LINE__ << ": " << #x << " = " << x << endl

#define int long long
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define contains(s,x) ((s).find(x) != (s).end())
const int MOD = 998244353;

int N, M, K;
vector<vector<int>> g;
vector<int> values, moments;
vector<map<int, int>> dp;

void add_value(map<int, int> &m, int t, int value) {
        m[t] += value;
        auto it = m.upper_bound(t);
        while (it != m.end() && it->ss < value) {
                value -= it->ss;
                m.erase(it);
                it = m.upper_bound(t);
        }
        if (it != m.end()) it->ss -= value;
}

void dfs(int v) {
        for (int u : g[v]) {
                dfs(u);
                if (sz(dp[u]) > sz(dp[v])) swap(dp[u], dp[v]);
                for (pii pr : dp[u]) dp[v][pr.ff] += pr.ss;
        }
        if (values[v] != -1) add_value(dp[v], moments[v], values[v]);
}

void solve() {
        cin >> N >> M >> K;
        g.assign(N, {});
        values.assign(N, -1);
        moments.assign(N, -1);
        dp.assign(N, {});
        for (int i = 1; i < N; i++) {
                int v;
                cin >> v;
                v--;
                g[v].pb(i);
        }
        for (int i = 0; i < M; i++) {
                int v, t, w;
                cin >> v >> t >> w;
                v--;
                moments[v] = t;
                values[v] = w;
        }
        dfs(0);
        int ans = 0;
        for (pii pr : dp[0]) ans += pr.ss;
        cout << ans << endl;
}

int32_t main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);

        int t = 1;
        // cin >> t;
        while (t--) {
                solve();
        }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 19480 KB Output is correct
2 Correct 36 ms 20560 KB Output is correct
3 Correct 119 ms 38224 KB Output is correct
4 Correct 59 ms 21096 KB Output is correct
5 Correct 78 ms 23148 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 49 ms 26448 KB Output is correct
5 Correct 61 ms 30548 KB Output is correct
6 Correct 59 ms 26596 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 16640 KB Output is correct
2 Correct 40 ms 15700 KB Output is correct
3 Correct 38 ms 19660 KB Output is correct
4 Correct 30 ms 17100 KB Output is correct
5 Correct 37 ms 26704 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 55 ms 20020 KB Output is correct
11 Correct 62 ms 18812 KB Output is correct
12 Correct 40 ms 19156 KB Output is correct
13 Correct 29 ms 16368 KB Output is correct
14 Correct 38 ms 26048 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2652 KB Output is correct
2 Correct 19 ms 11688 KB Output is correct
3 Correct 20 ms 11536 KB Output is correct
4 Correct 21 ms 11612 KB Output is correct
5 Correct 8 ms 10456 KB Output is correct
6 Correct 19 ms 13916 KB Output is correct
7 Correct 21 ms 17248 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 49 ms 26448 KB Output is correct
14 Correct 61 ms 30548 KB Output is correct
15 Correct 59 ms 26596 KB Output is correct
16 Correct 55 ms 20020 KB Output is correct
17 Correct 62 ms 18812 KB Output is correct
18 Correct 40 ms 19156 KB Output is correct
19 Correct 29 ms 16368 KB Output is correct
20 Correct 38 ms 26048 KB Output is correct
21 Correct 14 ms 5980 KB Output is correct
22 Correct 52 ms 21320 KB Output is correct
23 Correct 65 ms 25624 KB Output is correct
24 Correct 109 ms 37460 KB Output is correct
25 Correct 61 ms 20400 KB Output is correct
26 Correct 88 ms 23124 KB Output is correct
27 Correct 64 ms 21844 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 46 ms 19480 KB Output is correct
11 Correct 36 ms 20560 KB Output is correct
12 Correct 119 ms 38224 KB Output is correct
13 Correct 59 ms 21096 KB Output is correct
14 Correct 78 ms 23148 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 49 ms 26448 KB Output is correct
19 Correct 61 ms 30548 KB Output is correct
20 Correct 59 ms 26596 KB Output is correct
21 Correct 44 ms 16640 KB Output is correct
22 Correct 40 ms 15700 KB Output is correct
23 Correct 38 ms 19660 KB Output is correct
24 Correct 30 ms 17100 KB Output is correct
25 Correct 37 ms 26704 KB Output is correct
26 Correct 55 ms 20020 KB Output is correct
27 Correct 62 ms 18812 KB Output is correct
28 Correct 40 ms 19156 KB Output is correct
29 Correct 29 ms 16368 KB Output is correct
30 Correct 38 ms 26048 KB Output is correct
31 Correct 4 ms 2652 KB Output is correct
32 Correct 19 ms 11688 KB Output is correct
33 Correct 20 ms 11536 KB Output is correct
34 Correct 21 ms 11612 KB Output is correct
35 Correct 8 ms 10456 KB Output is correct
36 Correct 19 ms 13916 KB Output is correct
37 Correct 21 ms 17248 KB Output is correct
38 Correct 14 ms 5980 KB Output is correct
39 Correct 52 ms 21320 KB Output is correct
40 Correct 65 ms 25624 KB Output is correct
41 Correct 109 ms 37460 KB Output is correct
42 Correct 61 ms 20400 KB Output is correct
43 Correct 88 ms 23124 KB Output is correct
44 Correct 64 ms 21844 KB Output is correct
45 Correct 14 ms 5720 KB Output is correct
46 Correct 53 ms 20820 KB Output is correct
47 Correct 63 ms 24400 KB Output is correct
48 Correct 110 ms 34332 KB Output is correct
49 Correct 56 ms 21456 KB Output is correct
50 Correct 88 ms 23124 KB Output is correct
51 Correct 65 ms 21864 KB Output is correct