oj.uz

Submission #582636

# Submission time Handle Problem Language Result Execution time Memory
582636 2022-06-24T07:49:58 Z 반딧불(#8370) Magic Tree (CEOI19_magictree) C++17
45 / 100
 2000 ms 19680 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int lc[800002], rc[800002], cnt[800002];
ll sum[800002];
int nodeCnt;
int nodeVec[800002], nodeVecCnt;

inline int newCnt(){
    return nodeVecCnt ? nodeVec[--nodeVecCnt] : ++nodeCnt;
}

void update(int i, int l, int r, int x, ll v){ /// v��ŭ ���Ѵ�
    if(l==r){
        sum[i] += v;
        if(!cnt[i]) cnt[i]++;
        return;
    }
    int m = (l+r)>>1;
    if(x<=m){
        if(!lc[i]) lc[i] = newCnt();
        update(lc[i], l, m, x, v);
    }
    else{
        if(!rc[i]) rc[i] = newCnt();
        update(rc[i], m+1, r, x, v);
    }
    sum[i] = (lc[i] ? sum[lc[i]] : 0) + (rc[i] ? sum[rc[i]] : 0);
    cnt[i] = (lc[i] ? cnt[lc[i]] : 0) + (rc[i] ? cnt[rc[i]] : 0);
}

ll query(int i, int l, int r, int s, int e){
    if(r<s || e<l) return 0;
    if(s<=l && r<=e) return sum[i];
    int m = (l+r)>>1;
    ll ret = 0;
    if(s<=m && lc[i]) ret += query(lc[i], l, m, s, e);
    if(m<e && rc[i]) ret += query(rc[i], m+1, r, s, e);
    return ret;
}

void deleteNode(int x){
    if(lc[x]){
        deleteNode(lc[x]);
        lc[x] = 0;
    }
    if(rc[x]){
        deleteNode(rc[x]);
        rc[x] = 0;
    }
    cnt[x] = sum[x] = 0;
    nodeVec[nodeVecCnt++] = x;
}

bool nextRemove(int i, int l, int r, int x, ll &v){
    if(r<x) return false;
    if(l==r){
        ll tmp = min(sum[i], v);
        sum[i] -= tmp;
        v -= tmp;
        if(!sum[i]){
            deleteNode(i);
            return true;
        }
        return false;
    }
    int m = (l+r)>>1;
    if(lc[i] && sum[lc[i]]){
        if(nextRemove(lc[i], l, m, x, v)) lc[i] = 0;
    }
    if(v && rc[i] && sum[rc[i]]){
        if(nextRemove(rc[i], m+1, r, x, v)) rc[i] = 0;
    }
    sum[i] = (lc[i] ? sum[lc[i]] : 0) + (rc[i] ? sum[rc[i]] : 0);
    cnt[i] = (lc[i] ? cnt[lc[i]] : 0) + (rc[i] ? cnt[rc[i]] : 0);
    if(!sum[i]){
        deleteNode(i);
        return true;
    }
    return false;
}

void mergeSet(int A, int B, int l, int r){
    if(l==r){
        sum[A] += sum[B];
        return;
    }
    int m = (l+r)>>1;
    if(lc[B]){
        if(!lc[A]) lc[A] = newCnt();
        mergeSet(lc[A], lc[B], l, m);
    }
    if(rc[B]){
        if(!rc[A]) rc[A] = newCnt();
        mergeSet(rc[A], rc[B], m+1, r);
    }
    sum[A] = (lc[A] ? sum[lc[A]] : 0) + (rc[A] ? sum[rc[A]] : 0);
}

struct Fruit{
    int v, d; ll w;
    Fruit(){}
    Fruit(int v, int d, ll w): v(v), d(d), w(w){}
};

int n, m, k;
int par[100002];
vector<int> child[100002];
int state[100002];
Fruit fruit[100002];

int day[100002];
ll weight[100002];
int root[100002];

void renumber(){
    vector<int> dVec;
    for(int i=1; i<=m; i++) dVec.push_back(fruit[i].d);
    sort(dVec.begin(), dVec.end());
    dVec.erase(unique(dVec.begin(), dVec.end()), dVec.end());
    for(int i=1; i<=m; i++) fruit[i].d = lower_bound(dVec.begin(), dVec.end(), fruit[i].d) - dVec.begin() + 1;
    k = (int)dVec.size();
}

void dfs(int x){
    root[x] = newCnt();
    for(auto y: child[x]){
        dfs(y);
        if(cnt[x] > cnt[y]) mergeSet(root[x], root[y], 1, k);
        else mergeSet(root[y], root[x], 1, k), swap(root[x], root[y]);
        deleteNode(root[y]);
        root[y] = 0;
    }
    if(day[x]){
        ll v = query(root[x], 1, k, 1, day[x]-1);
        update(root[x], 1, k, day[x], weight[x]);
        v = weight[x];
        nextRemove(root[x], 1, k, day[x]+1, v);
//            printf("%d: %lld\n", x, v);
    }
}

int main(){
    scanf("%d %d %d", &n, &m, &k);
    for(int i=2; i<=n; i++){
        scanf("%d", &par[i]);
        child[par[i]].push_back(i);
    }

    for(int i=1; i<=m; i++){
        int v, d, w;
        scanf("%d %d %d", &v, &d, &w);
        fruit[i] = Fruit(v, d, w);
    }
    renumber();
    for(int i=1; i<=m; i++){
        day[fruit[i].v] = fruit[i].d;
        weight[fruit[i].v] = fruit[i].w;
    }

    dfs(1);

    printf("%lld", query(root[1], 1, k, 1, k));
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:147:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         scanf("%d", &par[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
magictree.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         scanf("%d %d %d", &v, &d, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 8568 KB Output is correct
2 Execution timed out 2083 ms 11480 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 92 ms 19544 KB Output is correct
5 Correct 87 ms 19680 KB Output is correct
6 Correct 131 ms 19500 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 7792 KB Output is correct
2 Correct 64 ms 7740 KB Output is correct
3 Correct 61 ms 12736 KB Output is correct
4 Correct 41 ms 6512 KB Output is correct
5 Correct 79 ms 18668 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 108 ms 7824 KB Output is correct
11 Correct 95 ms 7784 KB Output is correct
12 Correct 82 ms 12704 KB Output is correct
13 Correct 57 ms 6460 KB Output is correct
14 Correct 63 ms 18956 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3456 KB Output is correct
2 Correct 44 ms 6332 KB Output is correct
3 Correct 44 ms 6220 KB Output is correct
4 Correct 46 ms 6240 KB Output is correct
5 Execution timed out 2048 ms 5296 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 3 ms 2772 KB Output is correct
13 Correct 92 ms 19544 KB Output is correct
14 Correct 87 ms 19680 KB Output is correct
15 Correct 131 ms 19500 KB Output is correct
16 Correct 108 ms 7824 KB Output is correct
17 Correct 95 ms 7784 KB Output is correct
18 Correct 82 ms 12704 KB Output is correct
19 Correct 57 ms 6460 KB Output is correct
20 Correct 63 ms 18956 KB Output is correct
21 Correct 64 ms 4100 KB Output is correct
22 Correct 256 ms 7528 KB Output is correct
23 Correct 531 ms 10064 KB Output is correct
24 Correct 942 ms 11980 KB Output is correct
25 Execution timed out 2083 ms 8052 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 1 ms 2644 KB Output is correct
9 Correct 1 ms 2644 KB Output is correct
10 Correct 362 ms 8568 KB Output is correct
11 Execution timed out 2083 ms 11480 KB Time limit exceeded
12 Halted 0 ms 0 KB -