Submission #242288

#TimeUsernameProblemLanguageResultExecution timeMemory
242288dwscMagic Tree (CEOI19_magictree)C++14
34 / 100
2129 ms796924 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int n,m,k; vector<int> adj[100010]; int ripe[100010]; int weight[100010]; int memo[100010][1010]; int dp(int u,int j){ if (j == 0) return 0; if (memo[u][j] != -1) return memo[u][j]; int s = 0; for (int i = 0; i < adj[u].size(); i++){ int v = adj[u][i]; s += dp(v,j); } if (j == ripe[u]) s += weight[u]; return memo[u][j] = max(s,dp(u,j-1)); } main(){ cin >> n >> m >> k; for (int i = 2; i <= n; i++){ int p; cin >> p; adj[p].push_back(i); } vector<int> temp; temp.push_back(0); for (int i = 0; i < m; i++){ int v,d,w; cin >> v >> d >> w; ripe[v] = d; weight[v] = w; temp.push_back(d); } sort(temp.begin(),temp.end()); temp.erase(unique(temp.begin(),temp.end()),temp.end()); for (int i = 1; i <= n; i++) ripe[i] = lower_bound(temp.begin(),temp.end(),ripe[i])-temp.begin(); //for (int i = 1; i <= n; i++) cout << ripe[i] << "\n"; for (int i = 1; i <= n; i++) for (int j = 0; j < temp.size(); j++) memo[i][j] = -1; cout << dp(1,temp.size()-1); }

Compilation message (stderr)

magictree.cpp: In function 'long long int dp(long long int, long long int)':
magictree.cpp:13:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < adj[u].size(); i++){
                     ~~^~~~~~~~~~~~~~~
magictree.cpp: At global scope:
magictree.cpp:20:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
magictree.cpp: In function 'int main()':
magictree.cpp:40:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i <= n; i++) for (int j = 0; j < temp.size(); j++) memo[i][j] = -1;
                                                  ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...