Submission #242317

#TimeUsernameProblemLanguageResultExecution timeMemory
242317dwscMagic Tree (CEOI19_magictree)C++14
37 / 100
2147 ms796804 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]; if (weight[u] != 0)return memo[u][j] = max(s,dp(u,j-1)); else return memo[u][j] = s; } 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 || m <= 1000){ 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); } else{ int ans = 0; for (int i = 1; i <= n; i++) ans += weight[i]; cout << ans; } }

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:21:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
magictree.cpp: In function 'int main()':
magictree.cpp:45:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < temp.size(); j++){
                         ~~^~~~~~~~~~~~~
#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...