oj.uz

Submission #1082114

# Submission time Handle Problem Language Result Execution time Memory
1082114 2024-08-30T17:30:32 Z dwuy Magic Tree (CEOI19_magictree) C++14
15 / 100
 98 ms 25028 KB 
/**         - dwuy -

　　　　　 ／＞　   フ
　　　　　 | 　_　 _|
　 　　　 ／`ミ _x ノ
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

**/
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) (int)((s).size())
#define MASK(k)(1LL<<(k))
#define TASK "test"
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 2+100005;

struct Node{
    int lz, sum;
};

struct SMT{
    int n;
    vector<Node> tree;

    SMT(int n = 0){
        this->n = n;
        this->tree.assign(n<<2|3, {0, 0});
    }

    void down(int id){
        if(tree[id].lz == 0) return;
        tree[id<<1].lz = tree[id<<1|1].lz = 1;
        tree[id<<1].sum = tree[id<<1|1].sum = 0;
        tree[id].lz = 0;
    }

    void update(int pos, int val){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            int mid = (lo + hi)>>1;
            down(id);
            if(pos <= mid) hi = mid, id = id<<1;
            else lo = mid + 1, id = id<<1|1;
        }
        tree[id].sum = val;
        for(id>>=1; id; id>>=1) tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;
    }

    void clear(int l, int r, int id, const int &u, const int &v){
        if(l > v || r < u) return;
        if(l >= u && r <= v){
            tree[id].sum = 0;
            tree[id].lz = 1;
            return;
        }
        down(id);
        int mid = (l + r)>>1;
        clear(l, mid, id<<1, u, v);
        clear(mid + 1, r, id<<1|1, u, v);
        tree[id].sum = tree[id<<1].sum + tree[id<<1|1].sum;
    }
 
    void clear(int l, int r){
        clear(1, n, 1, l, r);
    }
 

    int get(int l, int r, int id, const int &u, const int &v){
        if(l > v || r < u) return 0;
        if(l >= u && r <= v) return tree[id].sum;
        int mid = (l + r)>>1;
        return get(l, mid, id<<1, u, v) + get(mid + 1, r, id<<1|1, u, v);
    }

    int get(int l, int r){
        return get(1, n, 1, l, r);
    }
};

int n, m, k;
int dfsID = 0;  
int p[MX];
int h[MX];
int w[MX];
int num[MX];
int clo[MX];
vector<int> G[MX];
vector<int> T[MX];

void dfs(int u){
    h[u] = h[p[u]] + 1;
    num[u] = ++dfsID;
    for(int v: G[u]) dfs(v);
    clo[u] = dfsID;
}

int32_t main(){
    fastIO;
    //file(TASK);

    cin >> n >> m >> k;
    for(int i=2; i<=n; i++){
        cin >> p[i];
        G[p[i]].push_back(i);
    }
    for(int i=1; i<=m; i++){
        int u, d;
        cin >> u >> d;
        T[d].push_back(u);
        cin >> w[u];
    }

    dfs(1);
    SMT smt(n);
    int ans = 0;
    for(int i=k; i>=1; i--) if(T[i].size()){
        sort(T[i].begin(), T[i].end(), [&](const int &a, const int &b) -> bool {return h[a] > h[b];});
        vector<int> vt;
        for(int u: T[i]){
            int cost = smt.get(num[u] + 1, clo[u]);
            if(w[u] >= cost){
                ans += w[u] - cost;
                smt.clear(num[u], clo[u]);
                vt.push_back(u);
            }
            else smt.update(num[u], -w[u]);
        }
        for(int u: T[i]){
            smt.update(num[u], 0);
        }
        for(int u: vt){
            smt.update(num[u], w[u]);
        }
    }
    cout << ans;

    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 18780 KB Output is correct
2 Correct 44 ms 20048 KB Output is correct
3 Correct 93 ms 20816 KB Output is correct
4 Correct 78 ms 20180 KB Output is correct
5 Correct 91 ms 21132 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 20668 KB Output is correct
2 Correct 98 ms 21448 KB Output is correct
3 Correct 71 ms 22644 KB Output is correct
4 Correct 86 ms 19660 KB Output is correct
5 Correct 56 ms 25028 KB Output is correct

Subtask #5
0 / 16.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7516 KB Output is correct
2 Correct 25 ms 17732 KB Output is correct
3 Correct 24 ms 17756 KB Output is correct
4 Correct 29 ms 17748 KB Output is correct
5 Correct 19 ms 16344 KB Output is correct
6 Incorrect 21 ms 18176 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

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