oj.uz

Submission #702875

# Submission time Handle Problem Language Result Execution time Memory
702875 2023-02-25T09:20:31 Z jiahng Magic Tree (CEOI19_magictree) C++14
6 / 100
 163 ms 167616 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;
    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 (l != nullptr) ans += l->qry(a,b);
            if (r != nullptr) ans += r->qry(a,b);
            return ans;
        }
    }
    void upd(int p,int v){
        val += v;
        if (s == e) return;
        else if (p > m){
            if (r == nullptr) r = new node(m+1,e);
            r->upd(p,v);
        }else{
            if (l == nullptr) l = new node(s,m);
            l->upd(p,v);
        }
    }
}*root[maxn];

set <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){
        swap(root[x], root[mx]); st[x].swap(st[mx]);
    }else root[x] = new node(1,K);

    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
    if (DEBUG){
        cout << x << ' ' << '\n';
        aFOR(i, st[x]) cout << i.f << ' ' << i.s << '\n';
        cout << "\n\n";
    }
    
    st[x].insert(pi(D[x], W[x]));
    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 dp[1001][1001];
int dpf(int i,int j){
    if (dp[i][j] != -1) return dp[i][j];

    dp[i][j] = 0;
    aFOR(c, adj[i]) dp[i][j] += dpf(c,j);

    if (D[i] != 0 && j >= D[i]){
        int pos = W[i];
        aFOR(c, adj[i]) pos += dpf(c, D[i]);
        dp[i][j] = max(dp[i][j], pos);
    }
    return dp[i][j];
}
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;
    }
    mem(dp,-1);
    cout << dpf(1,K);
    //dfs(1);
    //cout << root[1]->qry(1,K);    
}
int32_t main(){
    fast;
    solve();
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 78540 KB Output is correct
2 Correct 36 ms 78584 KB Output is correct
3 Correct 36 ms 78584 KB Output is correct
4 Correct 35 ms 78580 KB Output is correct
5 Correct 34 ms 78540 KB Output is correct
6 Correct 34 ms 78540 KB Output is correct
7 Correct 40 ms 78580 KB Output is correct
8 Correct 35 ms 78540 KB Output is correct
9 Correct 36 ms 78544 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 117 ms 165864 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 78676 KB Output is correct
2 Correct 37 ms 78744 KB Output is correct
3 Correct 37 ms 78728 KB Output is correct
4 Incorrect 70 ms 85436 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 132 ms 166160 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 78540 KB Output is correct
2 Correct 36 ms 78584 KB Output is correct
3 Correct 36 ms 78584 KB Output is correct
4 Correct 35 ms 78580 KB Output is correct
5 Correct 34 ms 78540 KB Output is correct
6 Correct 34 ms 78540 KB Output is correct
7 Correct 40 ms 78580 KB Output is correct
8 Correct 35 ms 78540 KB Output is correct
9 Correct 36 ms 78544 KB Output is correct
10 Runtime error 163 ms 167616 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 133 ms 160596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 78540 KB Output is correct
2 Correct 36 ms 78584 KB Output is correct
3 Correct 36 ms 78584 KB Output is correct
4 Correct 35 ms 78580 KB Output is correct
5 Correct 34 ms 78540 KB Output is correct
6 Correct 34 ms 78540 KB Output is correct
7 Correct 40 ms 78580 KB Output is correct
8 Correct 35 ms 78540 KB Output is correct
9 Correct 36 ms 78544 KB Output is correct
10 Correct 36 ms 78676 KB Output is correct
11 Correct 37 ms 78744 KB Output is correct
12 Correct 37 ms 78728 KB Output is correct
13 Incorrect 70 ms 85436 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 78540 KB Output is correct
2 Correct 36 ms 78584 KB Output is correct
3 Correct 36 ms 78584 KB Output is correct
4 Correct 35 ms 78580 KB Output is correct
5 Correct 34 ms 78540 KB Output is correct
6 Correct 34 ms 78540 KB Output is correct
7 Correct 40 ms 78580 KB Output is correct
8 Correct 35 ms 78540 KB Output is correct
9 Correct 36 ms 78544 KB Output is correct
10 Runtime error 117 ms 165864 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -