oj.uz

Submission #242310

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

vector<int> AdjList[100005];

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

long long memo[100005][1005];

long long dfs2(int i, int k){
    if(k == 0){
        return 0;
    }

    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 += w[j];
        }else if(d[j] < k){
            tempVal = max(tempVal, w[j] + dfs2(j, d[j]));
        }

        temp2 += tempVal;
    }
    return temp2;
    //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 'long long int dfs2(int, int)':
magictree.cpp:17:15: warning: unused variable 'ans' [-Wunused-variable]
     long long ans = 0;
               ^~~
magictree.cpp: In function 'int main()':
magictree.cpp:41: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:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p);
         ~~~~~^~~~~~~~~~
magictree.cpp:58: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 6 ms 3072 KB Output is correct
2 Correct 6 ms 3072 KB Output is correct
3 Correct 8 ms 3072 KB Output is correct
4 Correct 7 ms 3072 KB Output is correct
5 Correct 7 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 6 ms 3072 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 5504 KB Output is correct
2 Correct 39 ms 5880 KB Output is correct
3 Correct 80 ms 5104 KB Output is correct
4 Correct 77 ms 4976 KB Output is correct
5 Correct 80 ms 5116 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 64 ms 7540 KB Output is correct
5 Correct 67 ms 7856 KB Output is correct
6 Correct 86 ms 7540 KB Output is correct

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 6132 KB Output is correct
2 Correct 82 ms 6132 KB Output is correct
3 Execution timed out 2076 ms 10088 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3072 KB Output is correct
2 Correct 6 ms 3072 KB Output is correct
3 Correct 8 ms 3072 KB Output is correct
4 Correct 7 ms 3072 KB Output is correct
5 Correct 7 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 6 ms 3072 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 231 ms 6132 KB Output is correct
11 Correct 180 ms 6132 KB Output is correct
12 Execution timed out 2069 ms 9964 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3584 KB Output is correct
2 Correct 76 ms 5512 KB Output is correct
3 Correct 62 ms 5496 KB Output is correct
4 Correct 65 ms 5504 KB Output is correct
5 Correct 20 ms 4344 KB Output is correct
6 Execution timed out 2092 ms 6776 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3072 KB Output is correct
2 Correct 6 ms 3072 KB Output is correct
3 Correct 8 ms 3072 KB Output is correct
4 Correct 7 ms 3072 KB Output is correct
5 Correct 7 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 6 ms 3072 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 6 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 64 ms 7540 KB Output is correct
14 Correct 67 ms 7856 KB Output is correct
15 Correct 86 ms 7540 KB Output is correct
16 Correct 231 ms 6132 KB Output is correct
17 Correct 180 ms 6132 KB Output is correct
18 Execution timed out 2069 ms 9964 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3072 KB Output is correct
2 Correct 6 ms 3072 KB Output is correct
3 Correct 8 ms 3072 KB Output is correct
4 Correct 7 ms 3072 KB Output is correct
5 Correct 7 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 6 ms 3072 KB Output is correct
9 Correct 6 ms 3072 KB Output is correct
10 Correct 47 ms 5504 KB Output is correct
11 Correct 39 ms 5880 KB Output is correct
12 Correct 80 ms 5104 KB Output is correct
13 Correct 77 ms 4976 KB Output is correct
14 Correct 80 ms 5116 KB Output is correct
15 Correct 6 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 64 ms 7540 KB Output is correct
19 Correct 67 ms 7856 KB Output is correct
20 Correct 86 ms 7540 KB Output is correct
21 Correct 126 ms 6132 KB Output is correct
22 Correct 82 ms 6132 KB Output is correct
23 Execution timed out 2076 ms 10088 KB Time limit exceeded
24 Halted 0 ms 0 KB -