Submission #599917

#TimeUsernameProblemLanguageResultExecution timeMemory
599917JomnoiMagic Tree (CEOI19_magictree)C++17
3 / 100
60 ms11820 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 1e5 + 5; const int MAX_K = 1e5 + 5; vector <pair <int, int>> riped[MAX_K]; vector <int> graph[MAX_N]; int parent[MAX_N]; int depth[MAX_N]; bool dead[MAX_N]; pair <int, int> fruit[MAX_N]; long long sum; void dfs(int u) { for(auto v : graph[u]) { depth[v] = depth[u] + 1; dfs(v); } } void dfs2(int u, int k) { if(dead[u] == true) { return; } if(fruit[u].first == k) { sum += fruit[u].second; } dead[u] = true; for(auto v : graph[u]) { dfs2(v, k); } } int main() { cin.tie(nullptr)->sync_with_stdio(false); int N, M, K; cin >> N >> M >> K; for(int i = 2; i <= N; i++) { cin >> parent[i]; graph[parent[i]].push_back(i); } dfs(1); long long ans = 0; bool sub2 = true; for(int i = 1; i <= M; i++) { int v, d, w; cin >> v >> d >> w; riped[d].emplace_back(v, w); fruit[v] = make_pair(d, w); if(graph[v].size() > 0) { sub2 = false; } ans += w; } if(sub2 == true) { cout << ans; return 0; } ans = 0; for(int i = 1; i <= K; i++) { sort(riped[i].begin(), riped[i].end(), [&](const pair <int, int> &a, const pair <int, int> &b) { return depth[a.first] > depth[b.first]; }); } for(int mask = 0; mask < (1<<K); mask++) { sum = 0; for(int i = 1; i <= N; i++) { dead[i] = false; } for(int k = 0; k < K; k++) { if(mask & (1<<k)) { for(auto [v, w] : riped[k + 1]) { dfs2(v, k + 1); } } } ans = max(ans, sum); } cout << ans; return 0; }
#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...