oj.uz

Submission #277935

# Submission time Handle Problem Language Result Execution time Memory
277935 2020-08-21T08:09:15 Z egekabas Magic Tree (CEOI19_magictree) C++14
9 / 100
 310 ms 28400 KB 
#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.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 23416 KB Output is correct
2 Correct 78 ms 25204 KB Output is correct
3 Correct 279 ms 28188 KB Output is correct
4 Correct 264 ms 27240 KB Output is correct
5 Correct 310 ms 28268 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5248 KB Output is correct
2 Incorrect 4 ms 5248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 28400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Incorrect 225 ms 27632 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 8448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Correct 6 ms 5248 KB Output is correct
11 Incorrect 4 ms 5248 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 4 ms 4992 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Correct 131 ms 23416 KB Output is correct
11 Correct 78 ms 25204 KB Output is correct
12 Correct 279 ms 28188 KB Output is correct
13 Correct 264 ms 27240 KB Output is correct
14 Correct 310 ms 28268 KB Output is correct
15 Correct 6 ms 5248 KB Output is correct
16 Incorrect 4 ms 5248 KB Output isn't correct
17 Halted 0 ms 0 KB -