oj.uz

Submission #579399

# Submission time Handle Problem Language Result Execution time Memory
579399 2022-06-19T04:54:36 Z talant117408 Magic Tree (CEOI19_magictree) C++17
34 / 100
 74 ms 33900 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 3 ms 4180 KB Output is correct
9 Correct 2 ms 4180 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4180 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 74 ms 24524 KB Output is correct
2 Correct 69 ms 24576 KB Output is correct
3 Correct 68 ms 28632 KB Output is correct
4 Correct 51 ms 23480 KB Output is correct
5 Correct 55 ms 33900 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 3 ms 4180 KB Output is correct
9 Correct 2 ms 4180 KB Output is correct
10 Correct 65 ms 24524 KB Output is correct
11 Correct 65 ms 24576 KB Output is correct
12 Correct 57 ms 28660 KB Output is correct
13 Correct 53 ms 23480 KB Output is correct
14 Correct 51 ms 33884 KB Output is correct

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 3 ms 4180 KB Output is correct
9 Correct 2 ms 4180 KB Output is correct
10 Incorrect 2 ms 4180 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 2 ms 4180 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 3 ms 4180 KB Output is correct
9 Correct 2 ms 4180 KB Output is correct
10 Incorrect 27 ms 6348 KB Output isn't correct
11 Halted 0 ms 0 KB -