oj.uz

Submission #868422

# Submission time Handle Problem Language Result Execution time Memory
868422 2023-10-31T13:06:07 Z Cookie Magic Tree (CEOI19_magictree) C++14
34 / 100
 2000 ms 18900 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("HCN.INP");
ofstream fout("HCN.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
//using u128 = __uint128_t;
//const int x[4] = {1, -1, 0, 0};
//const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 9;
const int mxn = 1e5 + 5, mxq = 2e5 + 5, sq = 200, mxv = 2e6 + 5;
const ll inf = 1e17 + 5;
//const int base= (1 << 18);
int n, m, k;
vt<int>adj[mxn + 1];
int day[mxn + 1];
ll cost[mxn + 1], dp[mxn + 1], pre[mxn + 1];
void ckmax(ll &a, ll b){
    a = max(a, b);
}
void dfs(int tme, int s){
    dp[s] = pre[s];
    ll tot = 0;
    for(auto i: adj[s]){
        dfs(tme, i);
        tot += dp[i];
    }
    ckmax(dp[s], tot);
    if(day[s] == tme)dp[s] += cost[s];
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 2; i <= n; i++){
        int p; cin >> p;
        adj[p].pb(i);
    }
    vt<int>care;
    for(int i = 0; i < m; i++){
        int v; cin >> v;
        cin >> day[v] >> cost[v];
        care.pb(day[v]);
    }
    sort(care.begin(), care.end());
    care.resize(unique(care.begin(), care.end()) - care.begin());
    
    ll ans = 0;
    for(int i = 0; i < sz(care); i++){
        dfs(care[i], 1);
        for(int j = 1; j <= n; j++){
            ckmax(ans, dp[j]);
            pre[j] = dp[j]; dp[j] = 0;
        }
    }
    cout << ans;
    return(0);
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2044 ms 7004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5464 KB Output is correct
2 Correct 6 ms 5468 KB Output is correct
3 Correct 5 ms 5380 KB Output is correct
4 Execution timed out 2053 ms 18900 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 7628 KB Output is correct
2 Correct 35 ms 7584 KB Output is correct
3 Correct 36 ms 11472 KB Output is correct
4 Correct 24 ms 6520 KB Output is correct
5 Correct 46 ms 16800 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 1 ms 5208 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 81 ms 7632 KB Output is correct
11 Correct 69 ms 7620 KB Output is correct
12 Correct 65 ms 11444 KB Output is correct
13 Correct 32 ms 6360 KB Output is correct
14 Correct 62 ms 16860 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 5852 KB Output is correct
2 Correct 1849 ms 7724 KB Output is correct
3 Correct 1850 ms 7724 KB Output is correct
4 Execution timed out 2067 ms 7516 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 1 ms 5208 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 5 ms 5464 KB Output is correct
11 Correct 6 ms 5468 KB Output is correct
12 Correct 5 ms 5380 KB Output is correct
13 Execution timed out 2053 ms 18900 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5208 KB Output is correct
3 Correct 1 ms 5212 KB Output is correct
4 Correct 1 ms 5212 KB Output is correct
5 Correct 1 ms 5212 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 1 ms 5208 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Execution timed out 2044 ms 7004 KB Time limit exceeded
11 Halted 0 ms 0 KB -