oj.uz

Submission #928239

# Submission time Handle Problem Language Result Execution time Memory
928239 2024-02-16T05:48:05 Z vjudge1 Magic Tree (CEOI19_magictree) C++17
34 / 100
 2000 ms 95060 KB 
#include<bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define ll long long
#define maksim gay
#define int ll
#define pb push_back
#define sz(s) (int)s.size()
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))
#define in insert
#define lb lower_bound
#define ub upper_bound

const int MAX=1e5+20;
const int inf=1e10;
const int N=2e5;

int n,m,k;
int dp[MAX][100];
int d[MAX],w[MAX];
vector<int> g[MAX];

void dfs(int v){
  for(auto to:g[v]){
    dfs(to);
    for(int j=0;j<=k;j++){
      dp[v][j]+=dp[to][j];
    }
  }
  dp[v][d[v]]+=w[v];
  for(int j=1;j<=k;j++){
    dp[v][j]=max(dp[v][j],dp[v][j-1]);
  }
  // cout<<"!! "<<v<<"\n";
  // for(int j=0;j<=k;j++){
  //   cout<<dp[v][j]<<" ";
  // }
  // cout<<"\n";
}

void solve(){
  cin>>n>>m>>k;
  for(int i=2;i<=n;i++){
    int p;
    cin>>p;
    g[p].pb(i);
  }
  for(int i=1;i<=m;i++){
    int v;
    cin>>v;
    cin>>d[v]>>w[v];
  }
  dfs(1);
  cout<<dp[1][k]<<"\n";
}


main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}

Compilation message

magictree.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main(){
      | ^~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 59536 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 84416 KB Output is correct
2 Correct 50 ms 84656 KB Output is correct
3 Correct 48 ms 88752 KB Output is correct
4 Correct 29 ms 83412 KB Output is correct
5 Correct 40 ms 95056 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4700 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 65 ms 84432 KB Output is correct
11 Correct 72 ms 84496 KB Output is correct
12 Correct 48 ms 88912 KB Output is correct
13 Correct 31 ms 83404 KB Output is correct
14 Correct 41 ms 95060 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 21336 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

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