oj.uz

답안 #582628

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
582628 2022-06-24T07:45:56 Z 반딧불(#8370) Magic Tree (CEOI19_magictree) C++17
45 / 100
 2000 ms 20160 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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 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 1 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 3 ms 2644 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 546 ms 9960 KB Output is correct
2 Execution timed out 2065 ms 11844 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 95 ms 19376 KB Output is correct
5 Correct 84 ms 20160 KB Output is correct
6 Correct 140 ms 19400 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 7628 KB Output is correct
2 Correct 78 ms 7540 KB Output is correct
3 Correct 58 ms 12532 KB Output is correct
4 Correct 38 ms 6460 KB Output is correct
5 Correct 62 ms 18504 KB Output is correct

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 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 1 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 3 ms 2644 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 102 ms 7556 KB Output is correct
11 Correct 79 ms 7652 KB Output is correct
12 Correct 78 ms 12620 KB Output is correct
13 Correct 51 ms 6452 KB Output is correct
14 Correct 58 ms 18900 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 3604 KB Output is correct
2 Correct 58 ms 6424 KB Output is correct
3 Correct 52 ms 6484 KB Output is correct
4 Correct 47 ms 6504 KB Output is correct
5 Execution timed out 2081 ms 5188 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 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 1 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 3 ms 2644 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 2 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 95 ms 19376 KB Output is correct
14 Correct 84 ms 20160 KB Output is correct
15 Correct 140 ms 19400 KB Output is correct
16 Correct 102 ms 7556 KB Output is correct
17 Correct 79 ms 7652 KB Output is correct
18 Correct 78 ms 12620 KB Output is correct
19 Correct 51 ms 6452 KB Output is correct
20 Correct 58 ms 18900 KB Output is correct
21 Correct 61 ms 3948 KB Output is correct
22 Correct 203 ms 7396 KB Output is correct
23 Correct 616 ms 11140 KB Output is correct
24 Correct 1016 ms 12992 KB Output is correct
25 Execution timed out 2088 ms 10792 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 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 1 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 3 ms 2644 KB Output is correct
8 Correct 3 ms 2644 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 546 ms 9960 KB Output is correct
11 Execution timed out 2065 ms 11844 KB Time limit exceeded
12 Halted 0 ms 0 KB -