oj.uz

Submission #582638

# Submission time Handle Problem Language Result Execution time Memory
582638 2022-06-24T07:51:04 Z 반딧불(#8370) Magic Tree (CEOI19_magictree) C++17
58 / 100
 2000 ms 25960 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];
        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:153:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |         scanf("%d", &par[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
magictree.cpp:161:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         scanf("%d %d %d", &v, &d, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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 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 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 314 ms 8424 KB Output is correct
2 Execution timed out 2062 ms 14100 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2900 KB Output is correct
2 Correct 2 ms 2900 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 93 ms 25784 KB Output is correct
5 Correct 90 ms 25960 KB Output is correct
6 Correct 160 ms 25860 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 7792 KB Output is correct
2 Correct 57 ms 7756 KB Output is correct
3 Correct 63 ms 15260 KB Output is correct
4 Correct 41 ms 6528 KB Output is correct
5 Correct 60 ms 24952 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 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 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 85 ms 7808 KB Output is correct
11 Correct 81 ms 7736 KB Output is correct
12 Correct 76 ms 15288 KB Output is correct
13 Correct 54 ms 6484 KB Output is correct
14 Correct 61 ms 25200 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3504 KB Output is correct
2 Correct 44 ms 6312 KB Output is correct
3 Correct 44 ms 6284 KB Output is correct
4 Correct 39 ms 6228 KB Output is correct
5 Correct 1874 ms 5244 KB Output is correct
6 Correct 712 ms 9308 KB Output is correct
7 Correct 162 ms 13732 KB Output is correct

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 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 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 3 ms 2900 KB Output is correct
11 Correct 2 ms 2900 KB Output is correct
12 Correct 2 ms 2900 KB Output is correct
13 Correct 93 ms 25784 KB Output is correct
14 Correct 90 ms 25960 KB Output is correct
15 Correct 160 ms 25860 KB Output is correct
16 Correct 85 ms 7808 KB Output is correct
17 Correct 81 ms 7736 KB Output is correct
18 Correct 76 ms 15288 KB Output is correct
19 Correct 54 ms 6484 KB Output is correct
20 Correct 61 ms 25200 KB Output is correct
21 Correct 55 ms 4100 KB Output is correct
22 Correct 182 ms 7504 KB Output is correct
23 Correct 468 ms 10124 KB Output is correct
24 Correct 787 ms 12120 KB Output is correct
25 Execution timed out 2087 ms 8392 KB Time limit exceeded
26 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 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 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 314 ms 8424 KB Output is correct
11 Execution timed out 2062 ms 14100 KB Time limit exceeded
12 Halted 0 ms 0 KB -