제출 #579399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
579399		talant117408	Magic Tree (CEOI19_magictree)	C++17	34 / 100	74 ms	33900 KiB

magictree

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int N = 1e5+7;
vector <int> graph[N];
int n, m, k;
pii hanging[N];

struct fruit {
    int vertex, day;
    ll weight;
};

vector <fruit> fruits(N);
ll dp[N][23];

void dfs(int v = 1) {
    if (hanging[v].first != 0) {
        dp[v][hanging[v].first] = hanging[v].second;
    }
    for (auto to : graph[v]) {
        dfs(to);
        for (int j = 1; j <= 20; j++) {
            dp[v][j] += dp[to][j];
        }
    }
    for (int j = 1; j <= 20; j++) {
        dp[v][j] = max(dp[v][j], dp[v][j-1]);
    }
}

void solve() {
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++) {
        int p; cin >> p;
        graph[p].pb(i);
    }
    for (int i = 1; i <= m; i++) {
        cin >> fruits[i].vertex >> fruits[i].day >> fruits[i].weight;
        hanging[fruits[i].vertex] = mp(fruits[i].day, fruits[i].weight);
    }
    
    if (k <= 20) {
        dfs();
        cout << dp[1][20];
    }
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17