oj.uz

Submission #834247

# Submission time Handle Problem Language Result Execution time Memory
834247 2023-08-22T12:13:40 Z bane Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 32436 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include <stack>
#include <iomanip>
using namespace std;
#define int long long
#define endl '\n'
vector<vector<int>>adj(100'001);
vector<pair<int,int>>fruits[100'001];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;


    for (int i = 0; i < n - 1; i++){
        int x; cin >> x; --x;
        adj[x].push_back(i+1);
        adj[i+1].push_back(x);
    }
    for (int i = 0; i < m; i++){
        int a,b,c;
        cin >> a >> b >> c;
        --a;
        fruits[a].push_back({b,c});
    }

    map<int,long long>dp[100'001];
    function<void(int,int)>dfs = [&](int u, int p){
        for(int& x : adj[u]){
            if (x == p)continue;
            dfs(x,u);
            for (auto j : dp[x]){
                dp[u][j.first] += j.second;
            }
            dp[x].clear();
        }

        //take this one
        if (fruits[u].size() > 0){
            long long res = fruits[u][0].second;
            while(res > 0){
                auto it = dp[u].upper_bound(fruits[u][0].first);
                if (it == dp[u].end()){
                    break;
                }
                if (it->second <= res){
                    res -= it->second;
                    dp[u].erase(it);
                }else{
                    it->second -= res;
                    break;
                }
            }
            dp[u][fruits[u][0].first] += fruits[u][0].second;
        }
    };
    dfs(0,0);
    long long ans = 0;
    for (auto j : dp[0])ans += j.second;
    cout << ans << endl;
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 16460 KB Output is correct
2 Execution timed out 2040 ms 20848 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 6 ms 9940 KB Output is correct
3 Correct 15 ms 9940 KB Output is correct
4 Correct 76 ms 31692 KB Output is correct
5 Execution timed out 2037 ms 32436 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 16664 KB Output is correct
2 Correct 68 ms 16464 KB Output is correct
3 Correct 66 ms 22348 KB Output is correct
4 Correct 49 ms 16576 KB Output is correct
5 Correct 56 ms 31460 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9728 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 87 ms 16548 KB Output is correct
11 Correct 68 ms 16440 KB Output is correct
12 Correct 123 ms 22384 KB Output is correct
13 Correct 40 ms 16548 KB Output is correct
14 Correct 115 ms 31308 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10668 KB Output is correct
2 Correct 35 ms 13616 KB Output is correct
3 Correct 34 ms 13652 KB Output is correct
4 Correct 35 ms 13684 KB Output is correct
5 Correct 17 ms 13896 KB Output is correct
6 Correct 227 ms 16868 KB Output is correct
7 Correct 222 ms 19560 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9728 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 ms 9940 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 15 ms 9940 KB Output is correct
13 Correct 76 ms 31692 KB Output is correct
14 Execution timed out 2037 ms 32436 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9728 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 65 ms 16460 KB Output is correct
11 Execution timed out 2040 ms 20848 KB Time limit exceeded
12 Halted 0 ms 0 KB -