Submission #277935

#	Time	Username	Problem	Language	Result	Execution time	Memory
277935		egekabas	Magic Tree (CEOI19_magictree)	C++14	9 / 100	310 ms	28400 KiB

magictree

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
struct tree{
    vector<ll> seg;
    vector<ll> lazy;
    void init(ll n){
        seg.resize(4*n+5);
        lazy.resize(4*n+5);
    }
    void push(ll v){
        if(lazy[v]){
            lazy[2*v] = 1;
            lazy[2*v+1] = 1;
            seg[2*v] = 0;
            seg[2*v+1] = 0;
            lazy[v] = 0;
        }
    }
    void erase(ll v, ll tl, ll tr, ll l, ll r){ 
        if(tr < l || r < tl)
            return;
        if(l <= tl && tr <= r){
            seg[v] = 0;
            lazy[v] = 1;
        }
        else{
            push(v);
            erase(2*v, tl, (tl+tr)/2, l, r);
            erase(2*v+1, (tl+tr)/2+1, tr, l, r);
        }
    }
    ll get(ll v, ll tl, ll tr, ll l, ll r){
        if(tr < l || r < tl)
            return 0;
        if(l <= tl && tr <= r)
            return seg[v];
        else{
            push(v);
            return get(2*v, tl, (tl+tr)/2, l, r)+get(2*v+1, (tl+tr)/2+1, tr, l, r);
        }
    }
    void upd(ll v, ll tl, ll tr, ll idx, ll val){
        if(tl == idx && tr == idx){
            seg[v] = val;
            return;
        }
        push(v);
        if(idx <= (tl+tr)/2)
            upd(2*v, tl, (tl+tr)/2, idx, val);
        else
            upd(2*v+1, (tl+tr)/2+1, tr, idx, val);
        seg[v] = seg[2*v]+seg[2*v+1];
    }
};
struct fruit{
    ll v, d, w;
} f[100009];
ll n, m, k;
vector<ll> g[100009];
ll curtime = 0;
ll tin[100009];
ll tout[100009];
void dfs(ll v){
    tin[v] = curtime++;
    for(auto u : g[v])
        dfs(u);
    tout[v] = curtime-1;
}
vector<pii> ar[100009];
ll sf(pii a, pii b){
    return tin[a.ff] > tin[b.ff];
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> m >> k;
    for(ll i = 2; i <= n; ++i){
        ll p;
        cin >> p;
        g[p].pb(i);
    }
    dfs(1);
    vector<ll> compress;
    for(ll i = 0; i < m; ++i){
        cin >> f[i].v >> f[i].d >> f[i].w;
        compress.pb(f[i].d);
    }
    sort(all(compress));
    compress.resize(unique(all(compress))-compress.begin());
    for(ll i = 0; i < m; ++i){
        ll time = lower_bound(all(compress), f[i].d)-compress.begin();
        ar[time].pb({f[i].v, f[i].w});
    }

    tree s1;
    tree s2;
    s1.init(n);
    s2.init(n);
    for(ll cur = compress.size()-1; cur >= 0; --cur){
        
        sort(all(ar[cur]), sf);
        s2.erase(1, 0, n-1, 0, n-1);
        for(auto u : ar[cur]){
            s2.upd(1, 0, n-1, tin[u.ff], u.ss);

            //cout << u.ff << ' ' << u.ss << '\n';
            //cout <<s2.get(1, 0, n-1, tin[u.ff], tout[u.ff]) << ' ' << s1.get(1, 0, n-1, tin[u.ff], tout[u.ff]) << '\n';
            //cout << '\n';
            if(s2.get(1, 0, n-1, tin[u.ff], tout[u.ff]) >= s1.get(1, 0, n-1, tin[u.ff], tout[u.ff])){
                s2.erase(1, 0, n-1, tin[u.ff], tout[u.ff]);
                s1.erase(1, 0, n-1, tin[u.ff], tout[u.ff]);
            }
        }
        for(auto u : ar[cur])
            if(s2.get(1, 0, n-1, tin[u.ff], tin[u.ff]) == 0){
                s1.upd(1, 0, n-1, tin[u.ff], u.ss);
            }
        
    }
    cout << s1.get(1, 0, n-1, 0, n-1);
}

• Subtask 1: 6 / 6
• Subtask 2: 3 / 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