Submission #1099471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099471		RiverFlow	Magic Tree (CEOI19_magictree)	C++14	100 / 100	140 ms	31864 KiB

magictree

#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

void prepare(); void main_code();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}

void prepare() {};

int n, m, k;

vector<int> g[N];

int s[N], ch[N], hd[N], pos[N], base[N], cnt = 0, cc = 0;

int h[N];

void dfs(int u) {
    s[u] = 1;
    for(int v : g[u])
        h[v] = h[u] + 1, dfs(v), s[u] += s[v];
}

void hld(int u) {
    ch[u] = cc;
    if (hd[cc] == 0) hd[cc] = u;
    pos[u] = ++cnt;
    base[cnt] = u;
    int mx = -1;
    for(int v : g[u]) {
        if (mx == -1 or s[mx] < s[v]) mx = v;
    }
    if (mx == -1) return ;
    hld(mx);
    for(int v : g[u]) {
        if (v != mx) {
            ++cc;
            hld(v);
        }
    }
}

vector<pair<int, int>> p[N];

template<typename T>
struct fenwick {
    int n; vector<T> bit; bool up = 0;
    fenwick() {};
    fenwick(int _n, bool _up) { n = _n; bit.resize(n + 7); up = _up; }
    void upd(int id, T val) {
        if (up) for(; id <= n; id += id & -id) bit[id] += val;
        else    for(; id  > 0; id -= id & -id) bit[id] += val;
    }
    void update(int l, int r, int val) {
//        cerr << "add: " << l << ' ' << r << ' ' << val << nl;
        upd(l, val);
        upd(r + 1, -val);
//        cerr << "bit[1]: " << bit[1] << nl;
    }
    T get(int id) {
        T ans = 0;
        if (up) for(; id  > 0; id -= id & -id) ans += bit[id];
        else    for(; id <= n; id += id & -id) ans += bit[id];
        return ans;
    }
};


int par[N];

long long val[N];

void main_code() {
    cin >> n >> m >> k;
    for(int i = 2; i <= n; ++i) {
        int p; cin >> p;
        par[i] = p;
        g[p].push_back(i);
    }
    dfs(1);
    hld(1);
    for(int i = 1; i <= m; ++i) {
        int v, d, w; cin >> v >> d >> w;
        p[d].push_back(_mp(v, w));
    }
//    FOR(i, 1, n) cout << pos[i] << ' '; cout << nl;
//    FOR(i, 1, n) cout << base[i] << ' '; cout << nl;
    set<int> cret;
    fenwick<long long> bit(n, 1);
    for(int i = 1; i <= k; ++i) if (sz(p[i])) {
        sort(all(p[i]), [&](ii x,ii y){
            return h[x.fi]<h[y.fi];
        });
//        cerr << "at: " << i << nl << nl;
//        for(auto j : p[i]) {
//            int x = pos[j.fi];
//            val[x] = bit.get(x);
////            val[pos[j.fi]]=
////                bit.get(pos[j.fi])-bit.get(pos[j].fi-1);
//        }
        for(auto j : p[i]) {
            // nhay len 1
            int v = j.first, w = j.second;
            int x = pos[v];
            val[x] = bit.get(x);
            // v la dinh

            for(;;) {

                int k = hd[ch[v]];
//                cerr << "v: " << v << ' ' << "k: " << k << ' ' << w << nl;

            if (sz(cret) and *cret.begin() <= pos[v]) {
                auto it = (--cret.upper_bound(pos[v]));
                while (it != cret.end() and *it >= pos[k] and *it <= pos[v]) {
                    int px = *it;
                    if (px < pos[v])
                        bit.update(px + 1, pos[v], w);
                    val[px] -= w;
//                    assert(pos[px] >= pos[k]);
//                    cerr << "px: " << px << v << ' ' << "k: " << k << ' ' << w << nl;
                    v = base[px];
//                    cerr << px << ' ' << val[px] << nl;
                    if (val[px] < 0) {
                        w = -val[px];
                        cret.erase(it);
                        if (sz(cret) == 0 or *cret.begin() > pos[v]) {
                            break ;
                        }
                        it = (--cret.lower_bound(pos[v]));
                        if (it == cret.end()
                        or *it < pos[k]) break ;
                    } else {
                        break ;
                    }
                }
                if (cret.find(pos[v]) != cret.end()) {
                    break ;
                }
            }
                bit.update(pos[k], pos[v], w);
                if (k == 1) break ;
                v = par[k];
            }



//            cret.insert(x);
//            val[x] = bit.get(x) - val[x];
//            if (x == 3) {
//                cerr << "val: " << val[x] << nl;
//            }
        }
//        for(auto j : p[i]) {
//            // ta cho cai gia tri cua no chi bi break
//            // khi nao ?
//
//        }
        for(auto j : p[i]) {
            int x = pos[j.fi];
            cret.insert(x);
            val[x] = j.se;
//            val[x] = bit.get(x) - val[x];
//            assert(val[x] > 0);
//            cret.insert(pos[j.fi]);
//            val[pos[j.fi]] = j.se;
//            val[pos[j.fi]] = (bit.get(pos[j].fi)-bit.get(pos[j].fi-1))-val[pos[j.fi]];
        }
    }
    cout << bit.get(1);

}


/*     Let the river flows naturally     */

Compilation message (stderr)

magictree.cpp: In function 'int main()':
magictree.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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