oj.uz

Submission #600054

# Submission time Handle Problem Language Result Execution time Memory
600054 2022-07-20T12:15:58 Z M_W Magic Tree (CEOI19_magictree) C++17
12 / 100
 160 ms 52660 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[200002];
long long dp[21][200002];
int t[200002], v[200002];
bool st3 = true;
int lis[200002], cnt;

void dfs(int a, int p){
    long long tmp[21];
    for(int i = 0; i <= 20; i++) tmp[i] = 0;

    for(auto x : adj[a]){
        dfs(x, a);
        for(int i = 0; i <= 20; i++){
            tmp[i] += dp[i][x];
        }
    }
    for(int i = 0; i <= 20; i++){
        if(i > 0) tmp[i] = max(tmp[i], tmp[i - 1]);

        if(i == t[a]) dp[i][a] = tmp[i] + v[a];
        else dp[i][a] = max(tmp[i], dp[max(0, i - 1)][a]);
    } 
    return;
}

int main(){
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    for(int i = 2, x; i <= N; i++){
        scanf("%d", &x);
        adj[x].push_back(i);

        if(x != i - 1) st3 = false;
    }
    for(int i = 0, x, y, z; i < M; i++){
        scanf("%d %d %d", &x, &y, &z);
        t[x] = y; v[x] = z;
        if(z != 1) st3 = false;
    }

    if(st3){
        int i = 1; while(t[i] == 0) i++;
        cnt = 0;
        if(t[i]){
            lis[0] = t[i];
            cnt++; i++;
        }
        for(; i <= N; i++){
            if(v[i] == 0) continue;
            int idx = upper_bound(lis, lis + cnt, t[i]) - lis;
            lis[idx] = t[i];

            if(idx == cnt) cnt++;
        }
        // for(int i = 0; i < cnt; i++) printf("%d ", lis[i]);
        printf("%d\n", cnt);
        return 0;
    }

    dfs(1, 1);
    long long ans = 0;
    for(int i = 0; i <= K; i++){
        ans = max(ans, dp[i][1]);
    }
    printf("%lld\n", ans);
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d %d %d", &N, &M, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
magictree.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%d %d %d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Incorrect 4 ms 5004 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 116 ms 49004 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5012 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 26064 KB Output is correct
2 Correct 160 ms 26072 KB Output is correct
3 Correct 85 ms 36920 KB Output is correct
4 Correct 54 ms 24596 KB Output is correct
5 Correct 68 ms 52660 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Incorrect 4 ms 5004 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 17924 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Incorrect 4 ms 5004 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Incorrect 4 ms 5004 KB Output isn't correct
6 Halted 0 ms 0 KB -