Submission #934476

#	Time	Username	Problem	Language	Result	Execution time	Memory
934476		sysia	Magic Tree (CEOI19_magictree)	C++17	0 / 100	91 ms	21484 KiB

magictree

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;
vector<int>sz, pre;

struct Tree{
    vector<int>tab;
    vector<bool>done;
    vector<vector<T>>where;
    int ans = 0, size = 1;
    
    Tree(int n){
        while (size < n) size*=2;
        done.assign(n+1, 0);
        tab.assign(2*size, 0);
        where.resize(2*size);
    }

    int query(int x){
        x += size;
        int ret = 0;
        while (x){
            ret += tab[x];
            x/=2;
        }
        return ret;
    }

    void undo(int x){
        x += size;
        while (x){
            for (auto [c, v]: where[x]){
                if (done[v]) continue;
                done[v] = 1;
                update(pre[v], pre[v]+sz[v]-1, -c);
            }
            where[x].clear();
            x/=2;
        }
    }

    void update(int l, int r, int c, int v = -1){
        debug(c);
        ans += c;
        for (l += size-1, r += size+1; r-l>1; l/=2, r/=2){
            if (!(l&1)) {
                tab[l+1] += c;
                if (v != -1) where[l+1].emplace_back(c, v);
            }
            if (r&1) {
                tab[r-1] += c;
                if (v != -1) where[r-1].emplace_back(c, v);
            }
        }
    }
};

void solve(){
    int n, m, k; cin >> n >> m >> k;
    vector<vector<int>>g(n+1);
    for (int i = 2; i<=n; i++){
        int p; cin >> p;
        g[p].emplace_back(i);
    }
    vector<vector<T>>que(k+1);
    for (int rep = 0; rep < m; rep++){
        int v, r, c; cin >> v >> r >> c;
        que[r].emplace_back(v, c);
    }
    sz.assign(n+1, 1);
    pre.resize(n+1);
    int tt = 0;
    function<void(int)>dfs = [&](int v){
        pre[v] = tt++;
        for (auto x: g[v]){
            dfs(x);
            sz[v] += sz[x];
        }
    };
    dfs(1);
    sort(que.begin(), que.end());
    Tree t(n+2);
    for (int day = 1; day <= k; day++){
        vector<bool>remove;
        for (auto [v, c]: que[day]){
            remove.emplace_back((t.query(v) <= c));
        }
        reverse(remove.begin(), remove.end());
        for (auto [v, c]: que[day]){
            bool what = remove.back(); remove.pop_back();
            if (what){
                //usuwamy wszystko na sciezce
                t.undo(pre[v]);
                t.update(pre[v], pre[v] + sz[v]-1, c, v);
            }
        }
    }
    cout << t.ans << "\n";
}


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

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

    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17