oj.uz

Submission #834239

# Submission time Handle Problem Language Result Execution time Memory
834239 2023-08-22T12:07:13 Z bane Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 35836 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){
                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 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 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 62 ms 16380 KB Output is correct
2 Execution timed out 2094 ms 21080 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 9812 KB Output is correct
2 Correct 7 ms 9940 KB Output is correct
3 Correct 14 ms 9940 KB Output is correct
4 Correct 68 ms 35020 KB Output is correct
5 Execution timed out 2052 ms 35836 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 16204 KB Output is correct
2 Correct 80 ms 17300 KB Output is correct
3 Correct 67 ms 23764 KB Output is correct
4 Correct 45 ms 17328 KB Output is correct
5 Correct 61 ms 33744 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 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 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 76 ms 17228 KB Output is correct
11 Correct 76 ms 17232 KB Output is correct
12 Correct 118 ms 23628 KB Output is correct
13 Correct 37 ms 17524 KB Output is correct
14 Correct 118 ms 34244 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10452 KB Output is correct
2 Correct 32 ms 14036 KB Output is correct
3 Correct 29 ms 14036 KB Output is correct
4 Correct 29 ms 14060 KB Output is correct
5 Correct 16 ms 13928 KB Output is correct
6 Correct 219 ms 17628 KB Output is correct
7 Correct 217 ms 20648 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 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 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 9812 KB Output is correct
11 Correct 7 ms 9940 KB Output is correct
12 Correct 14 ms 9940 KB Output is correct
13 Correct 68 ms 35020 KB Output is correct
14 Execution timed out 2052 ms 35836 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 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 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 62 ms 16380 KB Output is correct
11 Execution timed out 2094 ms 21080 KB Time limit exceeded
12 Halted 0 ms 0 KB -