oj.uz

Submission #834484

# Submission time Handle Problem Language Result Execution time Memory
834484 2023-08-22T14:49:36 Z Essa2006 Magic Tree (CEOI19_magictree) C++14
34 / 100
 334 ms 1048576 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
int n, m, k;
vector<int>P, Order;
vector<array<int, 2>>Q;
vector<vector<int>>A;
vector<vector<int>>dp;

void pre(){
    P.clear(), Order.clear(), Q.clear(), A.clear(), dp.clear();
    P.resize(n+1), Q.resize(n+1), A.resize(n+1), dp.resize(n+1, vector<int>(k+1));
}

void dfs(int u){
    for(int i=0;i<A[u].size();i++){
        int v=A[u][i];
        if(v!=P[u])
            dfs(v);
    }
    Order.push_back(u);
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>k;
    pre();
    for(int i=2;i<=n;i++){
        cin>>P[i];
        int u=i, v=P[i];
        A[u].push_back(v);
        A[v].push_back(u);
    }
    for(int j=0;j<m;j++){
        int v, d, c;
        cin>>v>>d>>c;
        Q[v]={d, c};
    }
    dfs(1);
    for(int kk=0;kk<n;kk++){
        int u=Order[kk];
        for(auto v:A[u]){
            if(v==P[u])
                continue;
            for(int i=1;i<=k;i++){
                dp[u][i]+=dp[v][i];
            }
        }
        if(Q[u][0]){
            dp[u][Q[u][0]]+=Q[u][1];
            for(int i=Q[u][0]+1;i<=k;i++){
                if(dp[u][i]>=dp[u][Q[u][0]])
                    break;
                dp[u][i]=dp[u][i-1];
            }
        }

    }
    int ans=dp[1][k];
    cout<<ans;
}

Compilation message

magictree.cpp: In function 'void dfs(long long int)':
magictree.cpp:21:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i=0;i<A[u].size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 334 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8300 KB Output is correct
2 Correct 4 ms 8276 KB Output is correct
3 Correct 4 ms 8276 KB Output is correct
4 Runtime error 300 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 15356 KB Output is correct
2 Correct 53 ms 15504 KB Output is correct
3 Correct 46 ms 17024 KB Output is correct
4 Correct 35 ms 16044 KB Output is correct
5 Correct 41 ms 19572 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 70 ms 29472 KB Output is correct
11 Correct 65 ms 21828 KB Output is correct
12 Correct 56 ms 31032 KB Output is correct
13 Correct 41 ms 30068 KB Output is correct
14 Correct 45 ms 33616 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 300 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 4 ms 8300 KB Output is correct
11 Correct 4 ms 8276 KB Output is correct
12 Correct 4 ms 8276 KB Output is correct
13 Runtime error 300 ms 1048576 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Runtime error 334 ms 1048576 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -