oj.uz

Submission #582658

# Submission time Handle Problem Language Result Execution time Memory
582658 2022-06-24T08:23:16 Z 반딧불(#8370) Magic Tree (CEOI19_magictree) C++17
58 / 100
 2000 ms 26404 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();
}

int vcnt;
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);
    }
//    if(++vcnt % 100 == 0) printf("vcnt %d %d %d\n", vcnt, nodeCnt, nodeVecCnt);
//    if(vcnt==10670){
//        puts("");
//    }
}

int main(){
//    freopen("output.txt", "r", stdin);
    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:161:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |         scanf("%d", &par[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
magictree.cpp:169:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         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 2720 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 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 261 ms 8524 KB Output is correct
2 Execution timed out 2079 ms 13744 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 89 ms 25996 KB Output is correct
5 Correct 90 ms 25916 KB Output is correct
6 Correct 164 ms 26404 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 7680 KB Output is correct
2 Correct 67 ms 7792 KB Output is correct
3 Correct 73 ms 15152 KB Output is correct
4 Correct 46 ms 6536 KB Output is correct
5 Correct 64 ms 24852 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 2720 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 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 123 ms 7808 KB Output is correct
11 Correct 72 ms 7780 KB Output is correct
12 Correct 75 ms 15240 KB Output is correct
13 Correct 52 ms 6452 KB Output is correct
14 Correct 67 ms 24940 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3412 KB Output is correct
2 Correct 44 ms 6304 KB Output is correct
3 Correct 40 ms 6276 KB Output is correct
4 Correct 43 ms 6260 KB Output is correct
5 Correct 13 ms 5196 KB Output is correct
6 Correct 1010 ms 9228 KB Output is correct
7 Correct 477 ms 13792 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 2720 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 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 89 ms 25996 KB Output is correct
14 Correct 90 ms 25916 KB Output is correct
15 Correct 164 ms 26404 KB Output is correct
16 Correct 123 ms 7808 KB Output is correct
17 Correct 72 ms 7780 KB Output is correct
18 Correct 75 ms 15240 KB Output is correct
19 Correct 52 ms 6452 KB Output is correct
20 Correct 67 ms 24940 KB Output is correct
21 Correct 58 ms 4100 KB Output is correct
22 Correct 187 ms 7524 KB Output is correct
23 Correct 515 ms 10576 KB Output is correct
24 Correct 964 ms 12652 KB Output is correct
25 Correct 133 ms 8820 KB Output is correct
26 Execution timed out 2067 ms 11812 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 2720 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 2 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 261 ms 8524 KB Output is correct
11 Execution timed out 2079 ms 13744 KB Time limit exceeded
12 Halted 0 ms 0 KB -