Submission #600054

#	Time	Username	Problem	Language	Result	Execution time	Memory
600054		M_W	Magic Tree (CEOI19_magictree)	C++17	12 / 100	160 ms	52660 KiB

magictree

#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 (stderr)

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
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 12 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17