oj.uz

Submission #702919

# Submission time Handle Problem Language Result Execution time Memory
702919 2023-02-25T10:10:12 Z jiahng Magic Tree (CEOI19_magictree) C++14
100 / 100
 424 ms 336680 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];
    auto it = st[x].upper_bound(pi(D[x], INF));
    while (cur > 0){
        if (it == st[x].end()) break;

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

    
    /*
    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 31 ms 70776 KB Output is correct
2 Correct 30 ms 70688 KB Output is correct
3 Correct 31 ms 70760 KB Output is correct
4 Correct 31 ms 70740 KB Output is correct
5 Correct 38 ms 70780 KB Output is correct
6 Correct 31 ms 70700 KB Output is correct
7 Correct 32 ms 70740 KB Output is correct
8 Correct 31 ms 70748 KB Output is correct
9 Correct 30 ms 70796 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 165156 KB Output is correct
2 Correct 109 ms 113928 KB Output is correct
3 Correct 424 ms 336680 KB Output is correct
4 Correct 226 ms 194936 KB Output is correct
5 Correct 331 ms 196344 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 70996 KB Output is correct
2 Correct 32 ms 71020 KB Output is correct
3 Correct 33 ms 71004 KB Output is correct
4 Correct 100 ms 103240 KB Output is correct
5 Correct 111 ms 109572 KB Output is correct
6 Correct 187 ms 105244 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 105424 KB Output is correct
2 Correct 173 ms 106444 KB Output is correct
3 Correct 122 ms 90712 KB Output is correct
4 Correct 111 ms 98844 KB Output is correct
5 Correct 97 ms 98332 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 70776 KB Output is correct
2 Correct 30 ms 70688 KB Output is correct
3 Correct 31 ms 70760 KB Output is correct
4 Correct 31 ms 70740 KB Output is correct
5 Correct 38 ms 70780 KB Output is correct
6 Correct 31 ms 70700 KB Output is correct
7 Correct 32 ms 70740 KB Output is correct
8 Correct 31 ms 70748 KB Output is correct
9 Correct 30 ms 70796 KB Output is correct
10 Correct 178 ms 123168 KB Output is correct
11 Correct 166 ms 116044 KB Output is correct
12 Correct 112 ms 91960 KB Output is correct
13 Correct 115 ms 117300 KB Output is correct
14 Correct 91 ms 95180 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 74620 KB Output is correct
2 Correct 67 ms 80332 KB Output is correct
3 Correct 65 ms 80460 KB Output is correct
4 Correct 73 ms 81228 KB Output is correct
5 Correct 46 ms 81724 KB Output is correct
6 Correct 62 ms 83444 KB Output is correct
7 Correct 60 ms 84592 KB Output is correct

Subtask #7
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 70776 KB Output is correct
2 Correct 30 ms 70688 KB Output is correct
3 Correct 31 ms 70760 KB Output is correct
4 Correct 31 ms 70740 KB Output is correct
5 Correct 38 ms 70780 KB Output is correct
6 Correct 31 ms 70700 KB Output is correct
7 Correct 32 ms 70740 KB Output is correct
8 Correct 31 ms 70748 KB Output is correct
9 Correct 30 ms 70796 KB Output is correct
10 Correct 31 ms 70996 KB Output is correct
11 Correct 32 ms 71020 KB Output is correct
12 Correct 33 ms 71004 KB Output is correct
13 Correct 100 ms 103240 KB Output is correct
14 Correct 111 ms 109572 KB Output is correct
15 Correct 187 ms 105244 KB Output is correct
16 Correct 178 ms 123168 KB Output is correct
17 Correct 166 ms 116044 KB Output is correct
18 Correct 112 ms 91960 KB Output is correct
19 Correct 115 ms 117300 KB Output is correct
20 Correct 91 ms 95180 KB Output is correct
21 Correct 73 ms 96520 KB Output is correct
22 Correct 218 ms 150088 KB Output is correct
23 Correct 230 ms 208500 KB Output is correct
24 Correct 386 ms 303108 KB Output is correct
25 Correct 232 ms 196296 KB Output is correct
26 Correct 256 ms 164212 KB Output is correct
27 Correct 204 ms 122076 KB Output is correct

Subtask #8
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 70776 KB Output is correct
2 Correct 30 ms 70688 KB Output is correct
3 Correct 31 ms 70760 KB Output is correct
4 Correct 31 ms 70740 KB Output is correct
5 Correct 38 ms 70780 KB Output is correct
6 Correct 31 ms 70700 KB Output is correct
7 Correct 32 ms 70740 KB Output is correct
8 Correct 31 ms 70748 KB Output is correct
9 Correct 30 ms 70796 KB Output is correct
10 Correct 173 ms 165156 KB Output is correct
11 Correct 109 ms 113928 KB Output is correct
12 Correct 424 ms 336680 KB Output is correct
13 Correct 226 ms 194936 KB Output is correct
14 Correct 331 ms 196344 KB Output is correct
15 Correct 31 ms 70996 KB Output is correct
16 Correct 32 ms 71020 KB Output is correct
17 Correct 33 ms 71004 KB Output is correct
18 Correct 100 ms 103240 KB Output is correct
19 Correct 111 ms 109572 KB Output is correct
20 Correct 187 ms 105244 KB Output is correct
21 Correct 167 ms 105424 KB Output is correct
22 Correct 173 ms 106444 KB Output is correct
23 Correct 122 ms 90712 KB Output is correct
24 Correct 111 ms 98844 KB Output is correct
25 Correct 97 ms 98332 KB Output is correct
26 Correct 178 ms 123168 KB Output is correct
27 Correct 166 ms 116044 KB Output is correct
28 Correct 112 ms 91960 KB Output is correct
29 Correct 115 ms 117300 KB Output is correct
30 Correct 91 ms 95180 KB Output is correct
31 Correct 39 ms 74620 KB Output is correct
32 Correct 67 ms 80332 KB Output is correct
33 Correct 65 ms 80460 KB Output is correct
34 Correct 73 ms 81228 KB Output is correct
35 Correct 46 ms 81724 KB Output is correct
36 Correct 62 ms 83444 KB Output is correct
37 Correct 60 ms 84592 KB Output is correct
38 Correct 73 ms 96520 KB Output is correct
39 Correct 218 ms 150088 KB Output is correct
40 Correct 230 ms 208500 KB Output is correct
41 Correct 386 ms 303108 KB Output is correct
42 Correct 232 ms 196296 KB Output is correct
43 Correct 256 ms 164212 KB Output is correct
44 Correct 204 ms 122076 KB Output is correct
45 Correct 94 ms 97828 KB Output is correct
46 Correct 188 ms 153488 KB Output is correct
47 Correct 251 ms 214056 KB Output is correct
48 Correct 421 ms 318864 KB Output is correct
49 Correct 241 ms 196988 KB Output is correct
50 Correct 317 ms 165572 KB Output is correct
51 Correct 221 ms 123060 KB Output is correct