oj.uz

Submission #965733

# Submission time Handle Problem Language Result Execution time Memory
965733 2024-04-19T06:27:27 Z vjudge1 Magic Tree (CEOI19_magictree) C++17
47 / 100
 2000 ms 45200 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 7<<14
#define int long long
vector<int>adj[N];
map<int,int> dp[N];
int d[N],w[N];
void dfs(int n){
    map<int,int> add;
    dp[n][0];
    for(auto i:adj[n]){
        dfs(i);
        if(size(dp[n])+size(add)<size(dp[i])) {
            add[0];
            auto it=++add.begin();
            while(it!=add.end()){
                it->second+=prev(it)->second;
                it++;
            }
            for(auto[i,j]:add)
                dp[n][i]=(--(dp[n].upper_bound(i)))->second;
            for(auto&[i,j]:dp[n])
                j+=(--(add.upper_bound(i)))->second;
            add.clear();
            swap(dp[n],dp[i]);
        }
        auto it=++dp[i].begin();
        while(it!=dp[i].end())
            add[it->first]+=it->second-prev(it)->second,it++;
        dp[i].clear();
    }
    add[0];
    auto it=++add.begin();
    while(it!=add.end()){
        it->second+=prev(it)->second;
        it++;
    }
    for(auto[i,j]:add)
        dp[n][i]=(--(dp[n].upper_bound(i)))->second;
    for(auto&[i,j]:dp[n])
        j+=(--(add.upper_bound(i)))->second;
    it=--(dp[n].upper_bound(d[n]));
    int val=it->second+w[n];
    dp[n][d[n]]=val;
    it=dp[n].find(d[n]);
    while(it!=dp[n].end()){
        it->second=max(it->second,val);
        it++;
    }
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m,k,Q;
    cin>>n>>m>>k;
    for(int i=2;i<=n;i++)
        cin>>Q,adj[Q].push_back(i);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        d[a]=b,w[a]=c;
    }
    dfs(1);
    cout<<(--dp[1].end())->second;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10120 KB Output is correct
2 Correct 3 ms 10076 KB Output is correct
3 Correct 3 ms 10076 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 3 ms 10076 KB Output is correct
6 Correct 2 ms 10076 KB Output is correct
7 Correct 2 ms 10124 KB Output is correct
8 Correct 3 ms 10076 KB Output is correct
9 Correct 2 ms 10072 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 14932 KB Output is correct
2 Execution timed out 2044 ms 25428 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10328 KB Output is correct
2 Correct 5 ms 10332 KB Output is correct
3 Correct 5 ms 10332 KB Output is correct
4 Execution timed out 2067 ms 44244 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 13392 KB Output is correct
2 Correct 56 ms 14164 KB Output is correct
3 Correct 57 ms 26912 KB Output is correct
4 Correct 34 ms 12800 KB Output is correct
5 Correct 57 ms 45200 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10120 KB Output is correct
2 Correct 3 ms 10076 KB Output is correct
3 Correct 3 ms 10076 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 3 ms 10076 KB Output is correct
6 Correct 2 ms 10076 KB Output is correct
7 Correct 2 ms 10124 KB Output is correct
8 Correct 3 ms 10076 KB Output is correct
9 Correct 2 ms 10072 KB Output is correct
10 Correct 79 ms 13656 KB Output is correct
11 Correct 70 ms 13624 KB Output is correct
12 Correct 76 ms 26260 KB Output is correct
13 Correct 34 ms 12248 KB Output is correct
14 Correct 80 ms 44732 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10844 KB Output is correct
2 Correct 31 ms 12808 KB Output is correct
3 Correct 28 ms 12636 KB Output is correct
4 Correct 37 ms 12644 KB Output is correct
5 Correct 16 ms 11484 KB Output is correct
6 Correct 138 ms 18524 KB Output is correct
7 Correct 300 ms 25388 KB Output is correct

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10120 KB Output is correct
2 Correct 3 ms 10076 KB Output is correct
3 Correct 3 ms 10076 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 3 ms 10076 KB Output is correct
6 Correct 2 ms 10076 KB Output is correct
7 Correct 2 ms 10124 KB Output is correct
8 Correct 3 ms 10076 KB Output is correct
9 Correct 2 ms 10072 KB Output is correct
10 Correct 6 ms 10328 KB Output is correct
11 Correct 5 ms 10332 KB Output is correct
12 Correct 5 ms 10332 KB Output is correct
13 Execution timed out 2067 ms 44244 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10120 KB Output is correct
2 Correct 3 ms 10076 KB Output is correct
3 Correct 3 ms 10076 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 3 ms 10076 KB Output is correct
6 Correct 2 ms 10076 KB Output is correct
7 Correct 2 ms 10124 KB Output is correct
8 Correct 3 ms 10076 KB Output is correct
9 Correct 2 ms 10072 KB Output is correct
10 Correct 82 ms 14932 KB Output is correct
11 Execution timed out 2044 ms 25428 KB Time limit exceeded
12 Halted 0 ms 0 KB -