Submission #598612

#TimeUsernameProblemLanguageResultExecution timeMemory
598612Valaki2Magic Tree (CEOI19_magictree)C++14
11 / 100
61 ms26616 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back const int maxn = 1e5; struct fruit { int vertex, day, weight; fruit() : vertex(0), day(0), weight(0) {} fruit(int vertex_, int day_, int weight_) : vertex(vertex_), day(day_), weight(weight_) {} }; int n, m, k; int par[maxn + 1]; vector<int> children[maxn + 1]; bool has_fruit[maxn + 1]; fruit fruit_of[maxn + 1]; vector<fruit> fruits; int d_ptr[maxn + 1]; vector<int> d[maxn + 1]; void dfs(int cur) { for(int nei : children[cur]) { dfs(nei); } d_ptr[cur] = cur; int which = 0; for(int nei : children[cur]) { if(d[d_ptr[nei]].size() > d[d_ptr[cur]].size()) { d_ptr[cur] = d_ptr[nei]; which = nei; } } for(int nei : children[cur]) { if(which != nei) { vector<int> v = d[d_ptr[nei]]; int v_size = v.size(); for(int i = 0; i < v_size; i++) { if(d[d_ptr[cur]][i] > v[i]) { d[d_ptr[cur]][i] = v[i]; } } } } if(has_fruit[cur]) { auto it = upper_bound(d[d_ptr[cur]].begin(), d[d_ptr[cur]].end(), fruit_of[cur].day); if(it == d[d_ptr[cur]].end()) { d[d_ptr[cur]].pb(fruit_of[cur].day); } else { *it = fruit_of[cur].day; } } } void solve() { cin >> n >> m >> k; for(int i = 2; i <= n; i++) { cin >> par[i]; children[par[i]].pb(i); } fruits.assign(m, fruit()); for(int i = 0; i < m; i++) { cin >> fruits[i].vertex >> fruits[i].day >> fruits[i].weight; has_fruit[fruits[i].vertex] = true; fruit_of[fruits[i].vertex] = fruits[i]; } dfs(1); cout << (int) (d[d_ptr[1]].size()) << "\n"; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); solve(); 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...