oj.uz

Submission #899430

# Submission time Handle Problem Language Result Execution time Memory
899430 2024-01-06T07:21:07 Z 12345678 Magic Tree (CEOI19_magictree) C++17
19 / 100
 2000 ms 26316 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e5+5;
ll n, m, k, t[nx], w[nx], tmp[nx], x, p, sm, ans;
vector<int> d[nx];

struct value
{
    ll time;
    mutable ll val, idx;
    bool operator< (const value &o) const 
    {
        return time<o.time;
    } 
};
multiset<value> ms[nx];

void dfs(int u)
{
    for (auto v:d[u]) dfs(v);
    for (auto v:d[u]) for (auto tmp:ms[v]) ms[u].insert(tmp);
    for (auto v:d[u]) ms[v].clear();
    sm=0;
    for (auto itr=ms[u].begin(); itr!=ms[u].end(); itr++)
    {
        sm+=itr->val-tmp[itr->idx];
        tmp[itr->idx]=itr->val;
        itr->val=sm;
        itr->idx=u;
    }
    if (!t[u]) {
        for (auto vl:ms[u]) ans=max(ans, vl.val);
        return;
    }
    value nw;
    nw.time=t[u]; nw.val=w[u]; nw.idx=u;
    auto itr=ms[u].upper_bound(nw);
    if (itr!=ms[u].begin()) nw.val+=prev(itr)->val;
    itr=ms[u].insert(nw);
    while (next(itr)!=ms[u].end()&&next(itr)->val<=itr->val) ms[u].erase(next(itr));
    for (auto vl:ms[u]) ans=max(ans, vl.val);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>k;
    for (int i=2; i<=n; i++) cin>>p, d[p].push_back(i);
    for (int i=1; i<=m; i++) cin>>x>>t[x]>>w[x];
    dfs(1);
    cout<<ans<<'\n';
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 3 ms 8796 KB Output is correct
3 Correct 18 ms 9028 KB Output is correct
4 Correct 66 ms 25472 KB Output is correct
5 Execution timed out 2065 ms 26316 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 21176 KB Output is correct
2 Correct 134 ms 22572 KB Output is correct
3 Execution timed out 2033 ms 17968 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 1 ms 8792 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 4 ms 8796 KB Output is correct
10 Correct 122 ms 19196 KB Output is correct
11 Correct 140 ms 19284 KB Output is correct
12 Execution timed out 2024 ms 17776 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9304 KB Output is correct
2 Correct 17 ms 11608 KB Output is correct
3 Correct 21 ms 11356 KB Output is correct
4 Correct 17 ms 11356 KB Output is correct
5 Correct 7 ms 10204 KB Output is correct
6 Correct 233 ms 13952 KB Output is correct
7 Correct 224 ms 17240 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 1 ms 8792 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 4 ms 8796 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct
11 Correct 3 ms 8796 KB Output is correct
12 Correct 18 ms 9028 KB Output is correct
13 Correct 66 ms 25472 KB Output is correct
14 Execution timed out 2065 ms 26316 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 1 ms 8792 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 4 ms 8796 KB Output is correct
10 Correct 55 ms 14164 KB Output is correct
11 Execution timed out 2040 ms 17188 KB Time limit exceeded
12 Halted 0 ms 0 KB -