Submission #242305

#TimeUsernameProblemLanguageResultExecution timeMemory
242305cheehengMagic Tree (CEOI19_magictree)C++14
48 / 100
2127 ms794228 KiB
#include <bits/stdc++.h> using namespace std; vector<int> AdjList[100005]; int d[100005]; long long w[100005]; int L[100005]; long long subtreeSum[100005][25]; // subtree rooted at i, day x void dfs1(int i, int x){ long long ans = (d[i] == x)*w[i]; for(int j: AdjList[i]){ dfs1(j, x); ans += subtreeSum[j][x]; } subtreeSum[i][x] = ans; } long long memo[100005][1005]; long long dfs2(int i, int k){ if(k == 0){ return 0; }else if(memo[i][k] != -1){ return memo[i][k]; } long long ans = 0; // delaying for 1 more day is acceptable //ans = dfs2(i, k-1); long long temp2 = 0; for(int j: AdjList[i]){ // either choose to cut or do not cut long long tempVal = dfs2(j, k); if(d[j] <= k){ tempVal = max(tempVal, w[j] + dfs2(j, d[j])); } temp2 += tempVal; } ans = max(ans, temp2); return memo[i][k] = ans; } int main(){ int n, m, k; scanf("%d%d%d", &n, &m, &k); bool subtask3 = true; for(int i = 2; i <= n; i ++){ int p; scanf("%d", &p); subtask3 &= (p == i-1); AdjList[p].push_back(i); } bool subtask2 = true; long long ans2 = 0; memset(d, -1, sizeof(d)); vector<int> xingchen; for(int i = 1; i <= m; i ++){ int x, y, z; scanf("%d%d%d", &x, &y, &z); subtask3 &= (z == 1); subtask2 &= AdjList[x].empty(); d[x] = y; w[x] = z; ans2 += w[x]; xingchen.push_back(d[x]); } sort(xingchen.begin(), xingchen.end()); xingchen.erase(unique(xingchen.begin(), xingchen.end()), xingchen.end()); for(int i = 1; i <= n; i ++){ if(d[i] == -1){continue;} d[i] = 1+lower_bound(xingchen.begin(), xingchen.end(), d[i]) - xingchen.begin(); //printf("d[%d]=%d\n", i, d[i]); } if(subtask2){ printf("%lld", ans2); return 0; } if(subtask3){ int lis = 0; /*for(int i = n; i >= 2; i --){ printf("%d ", d[i]); } printf("\n");*/ for(int i = n; i >= 2; i --){ if(d[i] == -1){continue;} int pos = upper_bound(L, L+lis, d[i])-L; L[pos] = d[i]; if(pos == lis){ lis ++; } } printf("%d\n", lis); return 0; }else if((int)xingchen.size() <= 1001){ int K = xingchen.size(); /*for(int i = 0; i <= k; i ++){ dfs1(1, i); }*/ memset(memo, -1, sizeof(memo)); for(int i = 1; i <= n; i ++){ memo[i][0] = 0; } for(int k = 1; k <= K; k ++){ for(int i = n; i >= 1; i --){ long long temp2 = 0; for(int j: AdjList[i]){ // either choose to cut or do not cut long long tempVal = memo[j][k]; if(d[j] <= k){ tempVal = max(tempVal, w[j] + memo[j][d[j]]); } temp2 += tempVal; } memo[i][k] = temp2; } } printf("%lld\n", memo[1][K]); return 0; }else{ throw; } return 0; }

Compilation message (stderr)

magictree.cpp: In function 'int main()':
magictree.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p);
         ~~~~~^~~~~~~~~~
magictree.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &x, &y, &z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...