oj.uz

Submission #1083351

# Submission time Handle Problem Language Result Execution time Memory
1083351 2024-09-03T02:38:24 Z LucasLe Magic Tree (CEOI19_magictree) C++17
9 / 100
 81 ms 18268 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define dbg(v) "[" #v " = " << (v) << "]"
#define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define rep(i, l, r) for(int i = (l); i < (r); ++i)
 
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using ld = long double;
 
template<typename T> 
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }  return false;
    }
 
template<typename T>
    bool maximize(T& a, const T& b){    
        if(a < b){
            return a = b, true;
        } return false;
    }
 
template<int dimension, typename T>
struct tensor : public vector<tensor<dimension - 1, T>> {
    static_assert(dimension > 0, "Dimension must be positive !\n");
    template<typename... Args>
    tensor(int n = 0, Args... args) : vector<tensor<dimension - 1, T>> (n, tensor<dimension - 1, T>(args...)) {}
};
 
template<typename T>
struct tensor<1, T> : public vector<T> {
    tensor(int n = 0, T val = T()) : vector<T>(n, val) {}
};
 
const int MAX = 1e5 + 5;
 
int n, m, k, par[MAX], day[MAX], weight[MAX];
vector<int> adj[MAX];
map<int, ll> dp[MAX]; 

// we can prove that dp[u][t] <= dp[u][t + 1]
// notice : now the dp[u] works as the "difference array"
 
void dfs(int u) {
    for (int v : adj[u]) {
        dfs(v);
 
        if (sz(dp[u]) < sz(dp[v])) swap(dp[u], dp[v]);
        for (const auto& [pos, val] : dp[v]) {
            dp[u][pos] += val;
        }
 
        dp[v].clear();
    }
 
    if (day[u] && weight[u]) {
        
        ll sum = weight[u];
        ll lmouse = 0;
        bool f = true;

        while (true) {
            auto iter = dp[u].upper_bound(day[u]);
            if(iter == dp[u].end()) break;
 
            if (iter -> second <= sum) {
                sum -= iter -> second; //because of the max part
                lmouse += iter -> second;
                dp[u].erase(iter); //same dp[u][t]
            } else {
                // iter -> second -= sum; //can't increase
                iter -> second += lmouse;
                f = false;
                break; 
            }
        }
        
        if (f)
            dp[u][day[u]] += weight[u];
    }
}
 
// nh, yh
// u, day[u], weight[u] 
// yh += cnt[v][k] (k <= day[u])
// nh += max(cnt[v][k])
// res[u] = max(yh + weight[u], nh)

void testcase(){
    cin >> n >> m >> k;
    par[0] = -1;
    rep(i, 1, n){
        int p;
        cin >> p;
        --p;
        ::par[i] = p;
        adj[p].push_back(i);
    }
 
    rep(i, 0, m){
        int v, d, w;
        cin >> v >> d >> w;
        --v;
        day[v] = d;
        weight[v] = w;
    }
 
    dfs(0);
 
    ll sum = 0;
    for(auto it : dp[0]) sum += it.second;
    // cout << dp[0][2] << ' ' << dp[0][6] << '\n';
    cout << sum << '\n';
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    // file("task");
 
    int T = 1;
    //cin >> T;
    while(T--){
        testcase();
    }
 
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 13140 KB Output is correct
2 Correct 31 ms 18268 KB Output is correct
3 Correct 81 ms 16452 KB Output is correct
4 Correct 49 ms 14688 KB Output is correct
5 Correct 55 ms 16700 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 3 ms 7316 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7260 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 3 ms 7260 KB Output is correct
10 Incorrect 39 ms 11608 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8028 KB Output is correct
2 Correct 20 ms 10900 KB Output is correct
3 Correct 20 ms 10840 KB Output is correct
4 Correct 25 ms 10844 KB Output is correct
5 Correct 7 ms 9184 KB Output is correct
6 Incorrect 24 ms 13404 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 3 ms 7316 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7260 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 3 ms 7260 KB Output is correct
10 Correct 4 ms 7516 KB Output is correct
11 Incorrect 3 ms 7516 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7260 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 3 ms 7316 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7260 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 3 ms 7260 KB Output is correct
10 Correct 38 ms 13140 KB Output is correct
11 Correct 31 ms 18268 KB Output is correct
12 Correct 81 ms 16452 KB Output is correct
13 Correct 49 ms 14688 KB Output is correct
14 Correct 55 ms 16700 KB Output is correct
15 Correct 4 ms 7516 KB Output is correct
16 Incorrect 3 ms 7516 KB Output isn't correct
17 Halted 0 ms 0 KB -