oj.uz

Submission #582639

# Submission time Handle Problem Language Result Execution time Memory
582639 2022-06-24T07:53:08 Z 반딧불(#8370) Magic Tree (CEOI19_magictree) C++17
58 / 100
 2000 ms 26040 KB 
#include <bits/stdc++.h>
#ifndef TEST
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#endif

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];
        if(!cnt[A]) cnt[A]=1;
        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);
    cnt[A] = (lc[A] ? cnt[lc[A]] : 0) + (rc[A] ? cnt[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:155:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:157:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         scanf("%d", &par[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
magictree.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |         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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 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 2 ms 2644 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 8532 KB Output is correct
2 Execution timed out 2079 ms 13856 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2900 KB Output is correct
2 Correct 2 ms 2900 KB Output is correct
3 Correct 3 ms 2836 KB Output is correct
4 Correct 109 ms 25780 KB Output is correct
5 Correct 92 ms 26040 KB Output is correct
6 Correct 147 ms 25760 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 7780 KB Output is correct
2 Correct 68 ms 7808 KB Output is correct
3 Correct 84 ms 15196 KB Output is correct
4 Correct 43 ms 6484 KB Output is correct
5 Correct 60 ms 24968 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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 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 2 ms 2644 KB Output is correct
10 Correct 115 ms 7796 KB Output is correct
11 Correct 91 ms 7780 KB Output is correct
12 Correct 83 ms 15236 KB Output is correct
13 Correct 49 ms 6500 KB Output is correct
14 Correct 66 ms 25184 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3412 KB Output is correct
2 Correct 33 ms 6336 KB Output is correct
3 Correct 35 ms 6300 KB Output is correct
4 Correct 39 ms 6292 KB Output is correct
5 Correct 15 ms 5104 KB Output is correct
6 Correct 686 ms 9360 KB Output is correct
7 Correct 186 ms 13844 KB Output is correct

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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 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 2 ms 2644 KB Output is correct
10 Correct 4 ms 2900 KB Output is correct
11 Correct 2 ms 2900 KB Output is correct
12 Correct 3 ms 2836 KB Output is correct
13 Correct 109 ms 25780 KB Output is correct
14 Correct 92 ms 26040 KB Output is correct
15 Correct 147 ms 25760 KB Output is correct
16 Correct 115 ms 7796 KB Output is correct
17 Correct 91 ms 7780 KB Output is correct
18 Correct 83 ms 15236 KB Output is correct
19 Correct 49 ms 6500 KB Output is correct
20 Correct 66 ms 25184 KB Output is correct
21 Correct 48 ms 4056 KB Output is correct
22 Correct 153 ms 7528 KB Output is correct
23 Correct 443 ms 10116 KB Output is correct
24 Correct 703 ms 12020 KB Output is correct
25 Correct 137 ms 8824 KB Output is correct
26 Execution timed out 2064 ms 13212 KB Time limit exceeded
27 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 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 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 2 ms 2644 KB Output is correct
10 Correct 234 ms 8532 KB Output is correct
11 Execution timed out 2079 ms 13856 KB Time limit exceeded
12 Halted 0 ms 0 KB -