oj.uz

Submission #582625

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

using namespace std;

typedef long long ll;

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

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

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:148:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         scanf("%d", &par[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
magictree.cpp:156:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         scanf("%d %d %d", &v, &d, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp: In function 'void update(int, int, int, int, ll)':
magictree.cpp:14:32: warning: array subscript -1 is below array bounds of 'int [10000002]' [-Warray-bounds]
   14 |     return nodeVec[--nodeVecCnt];
      |            ~~~~~~~~~~~~~~~~~~~~^
magictree.cpp:10:5: note: while referencing 'nodeVec'
   10 | int nodeVec[10000002], nodeVecCnt;
      |     ^~~~~~~
magictree.cpp:14:32: warning: array subscript -1 is below array bounds of 'int [10000002]' [-Warray-bounds]
   14 |     return nodeVec[--nodeVecCnt];
      |            ~~~~~~~~~~~~~~~~~~~~^
magictree.cpp:10:5: note: while referencing 'nodeVec'
   10 | int nodeVec[10000002], nodeVecCnt;
      |     ^~~~~~~
magictree.cpp: In function 'void mergeSet(int, int, int, int)':
magictree.cpp:14:32: warning: array subscript -1 is below array bounds of 'int [10000002]' [-Warray-bounds]
   14 |     return nodeVec[--nodeVecCnt];
      |            ~~~~~~~~~~~~~~~~~~~~^
magictree.cpp:10:5: note: while referencing 'nodeVec'
   10 | int nodeVec[10000002], nodeVecCnt;
      |     ^~~~~~~
magictree.cpp:14:32: warning: array subscript -1 is below array bounds of 'int [10000002]' [-Warray-bounds]
   14 |     return nodeVec[--nodeVecCnt];
      |            ~~~~~~~~~~~~~~~~~~~~^
magictree.cpp:10:5: note: while referencing 'nodeVec'
   10 | int nodeVec[10000002], nodeVecCnt;
      |     ^~~~~~~
magictree.cpp: In function 'void dfs(int)':
magictree.cpp:14:32: warning: array subscript -1 is below array bounds of 'int [10000002]' [-Warray-bounds]
   14 |     return nodeVec[--nodeVecCnt];
      |            ~~~~~~~~~~~~~~~~~~~~^
magictree.cpp:10:5: note: while referencing 'nodeVec'
   10 | int nodeVec[10000002], nodeVecCnt;
      |     ^~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2700 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2704 KB Output is correct
7 Correct 3 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 Runtime error 621 ms 487380 KB Execution killed with signal 11
2 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 2 ms 2900 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 93 ms 22336 KB Output is correct
5 Correct 85 ms 21672 KB Output is correct
6 Correct 136 ms 37652 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 11976 KB Output is correct
2 Correct 53 ms 9140 KB Output is correct
3 Correct 55 ms 14348 KB Output is correct
4 Correct 45 ms 13524 KB Output is correct
5 Correct 54 ms 18492 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2700 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2704 KB Output is correct
7 Correct 3 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 111 ms 30980 KB Output is correct
11 Correct 95 ms 22604 KB Output is correct
12 Correct 80 ms 31276 KB Output is correct
13 Correct 133 ms 98112 KB Output is correct
14 Correct 64 ms 18604 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11220 KB Output is correct
2 Correct 72 ms 21720 KB Output is correct
3 Correct 58 ms 21456 KB Output is correct
4 Correct 63 ms 26244 KB Output is correct
5 Runtime error 559 ms 485860 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2700 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2704 KB Output is correct
7 Correct 3 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 2 ms 2900 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 93 ms 22336 KB Output is correct
14 Correct 85 ms 21672 KB Output is correct
15 Correct 136 ms 37652 KB Output is correct
16 Correct 111 ms 30980 KB Output is correct
17 Correct 95 ms 22604 KB Output is correct
18 Correct 80 ms 31276 KB Output is correct
19 Correct 133 ms 98112 KB Output is correct
20 Correct 64 ms 18604 KB Output is correct
21 Correct 79 ms 40432 KB Output is correct
22 Correct 291 ms 133044 KB Output is correct
23 Runtime error 765 ms 488384 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2700 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2704 KB Output is correct
7 Correct 3 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 Runtime error 621 ms 487380 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -