oj.uz

Submission #582587

# Submission time Handle Problem Language Result Execution time Memory
582587 2022-06-24T06:33:37 Z 반딧불(#8370) Magic Tree (CEOI19_magictree) C++17
34 / 100
 2000 ms 968056 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    ll tree[400002];

    void update(int i, int l, int r, int x, ll v){
        if(l==r){
            tree[i] = max(tree[i], v);
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    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 tree[i];
        int m = (l+r)>>1;
        return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} tree;

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];

ll weight[100002][1002];
ll DP[100002][1002];

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){
    for(int i=1; i<=k; i++) DP[x][i] = weight[x][i];
    for(auto y: child[x]){
        dfs(y);
        for(int i=1; i<=k; i++){
            ll best = 0;
            for(int j=1; j<=i; j++){
                best = max(best, DP[y][j]);
            }
            DP[x][i] += best;
        }
    }
}

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++){
        weight[fruit[i].v][fruit[i].d] = fruit[i].w;
    }

    dfs(1);

    printf("%lld", *max_element(DP[1], DP[1]+k+1));
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d", &par[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
magictree.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         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 2772 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2760 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2105 ms 103352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 11860 KB Output is correct
2 Correct 90 ms 11900 KB Output is correct
3 Correct 85 ms 11868 KB Output is correct
4 Execution timed out 2146 ms 968056 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 770808 KB Output is correct
2 Correct 384 ms 769192 KB Output is correct
3 Correct 373 ms 774812 KB Output is correct
4 Correct 368 ms 769564 KB Output is correct
5 Correct 366 ms 780080 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 2772 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2760 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 432 ms 784852 KB Output is correct
11 Correct 393 ms 776980 KB Output is correct
12 Correct 407 ms 788804 KB Output is correct
13 Correct 411 ms 783660 KB Output is correct
14 Correct 368 ms 794148 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2096 ms 67716 KB Time limit exceeded
2 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 2772 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2760 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Correct 88 ms 11860 KB Output is correct
11 Correct 90 ms 11900 KB Output is correct
12 Correct 85 ms 11868 KB Output is correct
13 Execution timed out 2146 ms 968056 KB Time limit exceeded
14 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 2772 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 3 ms 2760 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 2 ms 2772 KB Output is correct
10 Execution timed out 2105 ms 103352 KB Time limit exceeded
11 Halted 0 ms 0 KB -