oj.uz

Submission #834242

# Submission time Handle Problem Language Result Execution time Memory
834242 2023-08-22T12:09:01 Z bane Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 33844 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'
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<vector<int>>adj(100'001);
    vector<pair<int,int>>fruits[100'001];

    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 9668 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 16240 KB Output is correct
2 Execution timed out 2029 ms 21216 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 14 ms 9948 KB Output is correct
4 Correct 70 ms 33076 KB Output is correct
5 Execution timed out 2087 ms 33844 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16244 KB Output is correct
2 Correct 88 ms 16212 KB Output is correct
3 Correct 91 ms 22800 KB Output is correct
4 Correct 39 ms 16320 KB Output is correct
5 Correct 53 ms 32804 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 9668 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 80 ms 16336 KB Output is correct
11 Correct 70 ms 16268 KB Output is correct
12 Correct 120 ms 22732 KB Output is correct
13 Correct 36 ms 16420 KB Output is correct
14 Correct 127 ms 32844 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10508 KB Output is correct
2 Correct 33 ms 13524 KB Output is correct
3 Correct 27 ms 13524 KB Output is correct
4 Correct 28 ms 13552 KB Output is correct
5 Correct 16 ms 13768 KB Output is correct
6 Correct 222 ms 17072 KB Output is correct
7 Correct 220 ms 20044 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 9668 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 4 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 14 ms 9948 KB Output is correct
13 Correct 70 ms 33076 KB Output is correct
14 Execution timed out 2087 ms 33844 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 9668 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 4 ms 9684 KB Output is correct
7 Correct 4 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 81 ms 16240 KB Output is correct
11 Execution timed out 2029 ms 21216 KB Time limit exceeded
12 Halted 0 ms 0 KB -