oj.uz

Submission #582623

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

using namespace std;

typedef long long ll;

int lc[20000002], rc[20000002], cnt[20000002];
ll sum[20000002];
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 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2660 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 333840 KB Output is correct
2 Runtime error 849 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 102 ms 22392 KB Output is correct
5 Correct 105 ms 21788 KB Output is correct
6 Correct 147 ms 37596 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 11964 KB Output is correct
2 Correct 56 ms 9192 KB Output is correct
3 Correct 64 ms 14272 KB Output is correct
4 Correct 52 ms 13536 KB Output is correct
5 Correct 60 ms 18552 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 3 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2660 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 112 ms 30928 KB Output is correct
11 Correct 88 ms 22584 KB Output is correct
12 Correct 89 ms 31268 KB Output is correct
13 Correct 146 ms 98076 KB Output is correct
14 Correct 65 ms 18604 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 11104 KB Output is correct
2 Correct 58 ms 22296 KB Output is correct
3 Correct 74 ms 22020 KB Output is correct
4 Correct 66 ms 26796 KB Output is correct
5 Runtime error 678 ms 1048576 KB Execution killed with signal 9
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 3 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2660 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 3 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 102 ms 22392 KB Output is correct
14 Correct 105 ms 21788 KB Output is correct
15 Correct 147 ms 37596 KB Output is correct
16 Correct 112 ms 30928 KB Output is correct
17 Correct 88 ms 22584 KB Output is correct
18 Correct 89 ms 31268 KB Output is correct
19 Correct 146 ms 98076 KB Output is correct
20 Correct 65 ms 18604 KB Output is correct
21 Correct 92 ms 40436 KB Output is correct
22 Correct 289 ms 133176 KB Output is correct
23 Runtime error 795 ms 1048576 KB Execution killed with signal 9
24 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 3 ms 2644 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 2 ms 2660 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 575 ms 333840 KB Output is correct
11 Runtime error 849 ms 1048576 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -