Submission #242309

#TimeUsernameProblemLanguageResultExecution timeMemory
242309dwscMagic Tree (CEOI19_magictree)C++14
34 / 100
365 ms425448 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(){ ios_base::sync_with_stdio(false); cin.tie(0); 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"; if (k <= 20){ for (int i = n; i >= 1; i--){ for (int j = 1; j < temp.size(); j++){ for (int x = 0; x < adj[i].size(); x++){ int v = adj[i][x]; memo[i][j] += memo[v][j]; } if (j == ripe[i]) memo[i][j] += weight[i]; memo[i][j] = max(memo[i][j],memo[i][j-1]); } } } else{ int ans = 0; for (int i = 1; i <= n; i++) ans += ripe[i]; cout << ans << "\n"; } 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:44:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < temp.size(); j++){
                         ~~^~~~~~~~~~~~~
magictree.cpp:45:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int x = 0; x < adj[i].size(); x++){
                             ~~^~~~~~~~~~~~~~~
#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...