oj.uz

Submission #834236

# Submission time Handle Problem Language Result Execution time Memory
834236 2023-08-22T12:06:35 Z bane Magic Tree (CEOI19_magictree) C++17
0 / 100
 2000 ms 21180 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] += res;
        }
    };
    dfs(0,0);
    long long ans = 0;
    for (auto j : dp[0])ans += j.second;
    cout << ans << endl;
    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 16292 KB Output is correct
2 Execution timed out 2037 ms 21180 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

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