oj.uz

Submission #242300

# Submission time Handle Problem Language Result Execution time Memory
242300 2020-06-27T08:31:40 Z cheeheng Magic Tree (CEOI19_magictree) C++14
48 / 100
 2000 ms 803568 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> AdjList[100005];

int d[100005];
long long w[100005];
int L[100005];

long long subtreeSum[100005][25];

// subtree rooted at i, day x
void dfs1(int i, int x){
    long long ans = (d[i] == x)*w[i];
    for(int j: AdjList[i]){
        dfs1(j, x);
        ans += subtreeSum[j][x];
    }

    subtreeSum[i][x] = ans;
}

long long memo[100005][1005];

long long dfs2(int i, int k){
    if(k == 0){
        return 0;
    }else if(memo[i][k] != -1){
        return memo[i][k];
    }

    long long ans = 0;
    // delaying for 1 more day is acceptable
    //ans = dfs2(i, k-1);

    long long temp2 = 0;
    for(int j: AdjList[i]){
        // either choose to cut or do not cut
        long long tempVal = dfs2(j, k);
        if(d[j] <= k){
            tempVal = max(tempVal, w[j] + dfs2(j, d[j]));
        }

        temp2 += tempVal;
    }
    ans = max(ans, temp2);

    return memo[i][k] = ans;
}

int main(){
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);

    bool subtask3 = true;
    for(int i = 2; i <= n; i ++){
        int p;
        scanf("%d", &p);
        subtask3 &= (p == i-1);

        AdjList[p].push_back(i);
    }

    bool subtask2 = true;
    long long ans2 = 0;
    memset(d, -1, sizeof(d));
    vector<int> xingchen;
    for(int i = 1; i <= m; i ++){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        subtask3 &= (z == 1);
        subtask2 &= AdjList[x].empty();
        d[x] = y;
        w[x] = z;
        ans2 += w[x];
        xingchen.push_back(d[x]);
    }
    sort(xingchen.begin(), xingchen.end());
    xingchen.erase(unique(xingchen.begin(), xingchen.end()), xingchen.end());

    for(int i = 1; i <= n; i ++){
        if(d[i] == -1){continue;}
        d[i] = 1+lower_bound(xingchen.begin(), xingchen.end(), d[i]) - xingchen.begin();
        //printf("d[%d]=%d\n", i, d[i]);
    }

    if(subtask2){
        printf("%lld", ans2);
        return 0;
    }

    if(subtask3){
        int lis = 0;
        /*for(int i = n; i >= 2; i --){
            printf("%d ", d[i]);
        }
        printf("\n");*/
        for(int i = n; i >= 2; i --){
            if(d[i] == -1){continue;}
            int pos = upper_bound(L, L+lis, d[i])-L;
            L[pos] = d[i];
            if(pos == lis){
                lis ++;
            }
        }
        printf("%d\n", lis);
        return 0;
    }else if((int)xingchen.size() <= 1001){
        k = xingchen.size();
        /*for(int i = 0; i <= k; i ++){
            dfs1(1, i);
        }*/

        memset(memo, -1, sizeof(memo));
        printf("%lld\n", dfs2(1, k));
        return 0;
    }else{
        throw;
    }

    return 0;
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p);
         ~~~~~^~~~~~~~~~
magictree.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 789752 KB Output is correct
2 Correct 363 ms 789880 KB Output is correct
3 Correct 373 ms 789816 KB Output is correct
4 Correct 365 ms 789752 KB Output is correct
5 Correct 6 ms 3072 KB Output is correct
6 Correct 6 ms 3072 KB Output is correct
7 Correct 6 ms 3072 KB Output is correct
8 Correct 377 ms 790136 KB Output is correct
9 Correct 372 ms 789884 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5496 KB Output is correct
2 Correct 44 ms 5888 KB Output is correct
3 Correct 81 ms 4980 KB Output is correct
4 Correct 78 ms 4976 KB Output is correct
5 Correct 90 ms 5136 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3072 KB Output is correct
2 Correct 6 ms 3072 KB Output is correct
3 Correct 6 ms 3072 KB Output is correct
4 Correct 63 ms 7540 KB Output is correct
5 Correct 66 ms 7924 KB Output is correct
6 Correct 85 ms 7540 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 792684 KB Output is correct
2 Correct 456 ms 792680 KB Output is correct
3 Correct 463 ms 797380 KB Output is correct
4 Correct 440 ms 791532 KB Output is correct
5 Correct 444 ms 803568 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 789752 KB Output is correct
2 Correct 363 ms 789880 KB Output is correct
3 Correct 373 ms 789816 KB Output is correct
4 Correct 365 ms 789752 KB Output is correct
5 Correct 6 ms 3072 KB Output is correct
6 Correct 6 ms 3072 KB Output is correct
7 Correct 6 ms 3072 KB Output is correct
8 Correct 377 ms 790136 KB Output is correct
9 Correct 372 ms 789884 KB Output is correct
10 Correct 523 ms 792688 KB Output is correct
11 Correct 496 ms 792816 KB Output is correct
12 Correct 486 ms 797292 KB Output is correct
13 Correct 430 ms 791408 KB Output is correct
14 Correct 63 ms 7548 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 790368 KB Output is correct
2 Correct 455 ms 792312 KB Output is correct
3 Correct 452 ms 792312 KB Output is correct
4 Correct 423 ms 792288 KB Output is correct
5 Correct 421 ms 791024 KB Output is correct
6 Correct 1131 ms 794488 KB Output is correct
7 Execution timed out 2134 ms 796792 KB Time limit exceeded

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 789752 KB Output is correct
2 Correct 363 ms 789880 KB Output is correct
3 Correct 373 ms 789816 KB Output is correct
4 Correct 365 ms 789752 KB Output is correct
5 Correct 6 ms 3072 KB Output is correct
6 Correct 6 ms 3072 KB Output is correct
7 Correct 6 ms 3072 KB Output is correct
8 Correct 377 ms 790136 KB Output is correct
9 Correct 372 ms 789884 KB Output is correct
10 Correct 7 ms 3072 KB Output is correct
11 Correct 6 ms 3072 KB Output is correct
12 Correct 6 ms 3072 KB Output is correct
13 Correct 63 ms 7540 KB Output is correct
14 Correct 66 ms 7924 KB Output is correct
15 Correct 85 ms 7540 KB Output is correct
16 Correct 523 ms 792688 KB Output is correct
17 Correct 496 ms 792816 KB Output is correct
18 Correct 486 ms 797292 KB Output is correct
19 Correct 430 ms 791408 KB Output is correct
20 Correct 63 ms 7548 KB Output is correct
21 Runtime error 53 ms 3840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 789752 KB Output is correct
2 Correct 363 ms 789880 KB Output is correct
3 Correct 373 ms 789816 KB Output is correct
4 Correct 365 ms 789752 KB Output is correct
5 Correct 6 ms 3072 KB Output is correct
6 Correct 6 ms 3072 KB Output is correct
7 Correct 6 ms 3072 KB Output is correct
8 Correct 377 ms 790136 KB Output is correct
9 Correct 372 ms 789884 KB Output is correct
10 Correct 50 ms 5496 KB Output is correct
11 Correct 44 ms 5888 KB Output is correct
12 Correct 81 ms 4980 KB Output is correct
13 Correct 78 ms 4976 KB Output is correct
14 Correct 90 ms 5136 KB Output is correct
15 Correct 7 ms 3072 KB Output is correct
16 Correct 6 ms 3072 KB Output is correct
17 Correct 6 ms 3072 KB Output is correct
18 Correct 63 ms 7540 KB Output is correct
19 Correct 66 ms 7924 KB Output is correct
20 Correct 85 ms 7540 KB Output is correct
21 Correct 488 ms 792684 KB Output is correct
22 Correct 456 ms 792680 KB Output is correct
23 Correct 463 ms 797380 KB Output is correct
24 Correct 440 ms 791532 KB Output is correct
25 Correct 444 ms 803568 KB Output is correct
26 Correct 523 ms 792688 KB Output is correct
27 Correct 496 ms 792816 KB Output is correct
28 Correct 486 ms 797292 KB Output is correct
29 Correct 430 ms 791408 KB Output is correct
30 Correct 63 ms 7548 KB Output is correct
31 Correct 385 ms 790368 KB Output is correct
32 Correct 455 ms 792312 KB Output is correct
33 Correct 452 ms 792312 KB Output is correct
34 Correct 423 ms 792288 KB Output is correct
35 Correct 421 ms 791024 KB Output is correct
36 Correct 1131 ms 794488 KB Output is correct
37 Execution timed out 2134 ms 796792 KB Time limit exceeded