oj.uz

Submission #702918

# Submission time Handle Problem Language Result Execution time Memory
702918 2023-02-25T10:08:15 Z jiahng Magic Tree (CEOI19_magictree) C++14
22 / 100
 2000 ms 336760 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 1000010
#define INF (ll)1e18
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
#define DEBUG 0


int TC,N,M,K;
int D[maxn],W[maxn];
vi adj[maxn];
int p;
struct node{
    int s,e,m;
    node *l=nullptr,*r=nullptr;
    bool linit=0,rinit=0;
    int val = 0;
    
    node(int ss,int ee){
        s = ss; e = ee; m = (s + e) / 2;
    }
    int qry(int a,int b){
        if (a <= s && e <= b) return val;
        else if (a > e || s > b) return 0;
        else{
            int ans = 0;
            if (linit) ans += l->qry(a,b);
            if (rinit) ans += r->qry(a,b);
            return ans;
        }
    }
    void upd(int p,int v){
        val += v;
        assert(val >= 0);
        if (s == e) return;
        else if (p > m){
            if (!rinit) r = new node(m+1,e);
            rinit = 1;
            r->upd(p,v);
        }else{
            if (!linit) l = new node(s,m);
            linit = 1;
            l->upd(p,v);
        }
    }
}*root[maxn];

multiset <pi> st[maxn];
void dfs(int x){
    int mx = -1;
    aFOR(i, adj[x]){
        dfs(i);
        if (mx == -1 || st[i].size() > st[mx].size()) mx = i;
    }
    if (mx != -1){
        root[x] = root[mx]; st[x].swap(st[mx]);
    }else{
        root[x] = new node(1,K); st[x].clear();
    }

    aFOR(i,adj[x]) if (i != mx){
        aFOR(j,st[i]){
            root[x]->upd(j.f, j.s);
            st[x].insert(j);
        }
    }
    if (D[x] == 0) return; // no fruit

    //int v = root[x]->qry(1,D[x]) + W[x];
    // update everything after D[x] by y -> max(y,v)
    
    //int pt = root[x]->bs(v); // earliest point where f(pt) >= v
    //int vpt = root[x]->qry(1, pt);

    root[x]->upd(D[x], W[x]); // shift up first, then flatten
    st[x].insert(pi(D[x], W[x]));
    if (DEBUG){
        cout << x << ' ' << '\n';
        aFOR(i, st[x]) cout << i.f << ' ' << i.s << '\n';
        cout << "\n\n";
    }
    
    int cur = W[x];
    while (cur > 0){
        auto it = st[x].upper_bound(pi(D[x], INF));
        if (it == st[x].end()) break;

        if (cur >= it->s){
            cur -= it->s;
            root[x]->upd(it->f, -it->s);
            st[x].erase(it);
        }else{
            root[x]->upd(it->f, -cur);
            pi tmp = *it;
            st[x].erase(it);
            st[x].insert(pi(tmp.f, tmp.s-cur));
            cur = 0;
        }
    }

    int sm = 0;
    auto it = st[x].begin();
    while (it != st[x].end()){
        int cur = it->f;
        while (it != st[x].end() && it->f == cur){
            sm += it->s; it++;
        }
        assert(sm == root[x]->qry(1,cur));
    }
}
void solve(){
    cin >> N >> M >> K;
    FOR(i,2,N){
        cin >> p; adj[p].pb(i);
    }
    int v,d,w;
    FOR(i,1,M){
        cin >> v >> d >> w;
        D[v] = d; W[v] = w;
    }
    dfs(1);
    cout << root[1]->val;
}
int32_t main(){
    fast;
    solve();
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70860 KB Output is correct
2 Correct 36 ms 70776 KB Output is correct
3 Correct 34 ms 70744 KB Output is correct
4 Correct 33 ms 70728 KB Output is correct
5 Correct 32 ms 70732 KB Output is correct
6 Correct 32 ms 70788 KB Output is correct
7 Correct 32 ms 70692 KB Output is correct
8 Correct 32 ms 70764 KB Output is correct
9 Correct 37 ms 70720 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 165304 KB Output is correct
2 Correct 111 ms 113980 KB Output is correct
3 Correct 430 ms 336760 KB Output is correct
4 Correct 241 ms 194880 KB Output is correct
5 Correct 326 ms 196424 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70996 KB Output is correct
2 Correct 36 ms 71064 KB Output is correct
3 Correct 39 ms 71016 KB Output is correct
4 Correct 154 ms 105156 KB Output is correct
5 Execution timed out 2079 ms 95772 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 105324 KB Output is correct
2 Correct 193 ms 108536 KB Output is correct
3 Execution timed out 2083 ms 85716 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70860 KB Output is correct
2 Correct 36 ms 70776 KB Output is correct
3 Correct 34 ms 70744 KB Output is correct
4 Correct 33 ms 70728 KB Output is correct
5 Correct 32 ms 70732 KB Output is correct
6 Correct 32 ms 70788 KB Output is correct
7 Correct 32 ms 70692 KB Output is correct
8 Correct 32 ms 70764 KB Output is correct
9 Correct 37 ms 70720 KB Output is correct
10 Correct 187 ms 124712 KB Output is correct
11 Correct 183 ms 117508 KB Output is correct
12 Execution timed out 2078 ms 90160 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 74608 KB Output is correct
2 Correct 65 ms 80264 KB Output is correct
3 Correct 69 ms 80436 KB Output is correct
4 Correct 65 ms 81220 KB Output is correct
5 Correct 55 ms 81836 KB Output is correct
6 Correct 69 ms 83360 KB Output is correct
7 Correct 66 ms 84728 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70860 KB Output is correct
2 Correct 36 ms 70776 KB Output is correct
3 Correct 34 ms 70744 KB Output is correct
4 Correct 33 ms 70728 KB Output is correct
5 Correct 32 ms 70732 KB Output is correct
6 Correct 32 ms 70788 KB Output is correct
7 Correct 32 ms 70692 KB Output is correct
8 Correct 32 ms 70764 KB Output is correct
9 Correct 37 ms 70720 KB Output is correct
10 Correct 32 ms 70996 KB Output is correct
11 Correct 36 ms 71064 KB Output is correct
12 Correct 39 ms 71016 KB Output is correct
13 Correct 154 ms 105156 KB Output is correct
14 Execution timed out 2079 ms 95772 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70860 KB Output is correct
2 Correct 36 ms 70776 KB Output is correct
3 Correct 34 ms 70744 KB Output is correct
4 Correct 33 ms 70728 KB Output is correct
5 Correct 32 ms 70732 KB Output is correct
6 Correct 32 ms 70788 KB Output is correct
7 Correct 32 ms 70692 KB Output is correct
8 Correct 32 ms 70764 KB Output is correct
9 Correct 37 ms 70720 KB Output is correct
10 Correct 182 ms 165304 KB Output is correct
11 Correct 111 ms 113980 KB Output is correct
12 Correct 430 ms 336760 KB Output is correct
13 Correct 241 ms 194880 KB Output is correct
14 Correct 326 ms 196424 KB Output is correct
15 Correct 32 ms 70996 KB Output is correct
16 Correct 36 ms 71064 KB Output is correct
17 Correct 39 ms 71016 KB Output is correct
18 Correct 154 ms 105156 KB Output is correct
19 Execution timed out 2079 ms 95772 KB Time limit exceeded
20 Halted 0 ms 0 KB -