Submission #776236

#TimeUsernameProblemLanguageResultExecution timeMemory
776236hazzleMagic Tree (CEOI19_magictree)C++17
23 / 100
81 ms23380 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> //#pragma GCC optimize("Ofast") //#pragma GCC optimize("avx2") using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define all(m) (m).begin(), (m).end() #define rall(m) (m).rbegin(), (m).rend() #define vec vector #define sz(a) (int) (a).size() #define mpp make_pair #define mtt make_tuple typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <ll, ll> pll; typedef pair <int, int> pii; typedef tuple <int, int, int> tui; template <typename T> using prq = priority_queue <T>; template <typename T> using pgq = priority_queue <T, vec <T>, greater <T>>; template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; } template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; } typedef struct node* pnode; struct node{ pnode l, r; ll s, p; node(ll s = 0, ll p = 0): s(s), p(p) { l = r = nullptr; } void apply(ll x){ umax(s, x), umax(p, x); } void push(){ if (!l) l = new node; if (!r) r = new node; if (!p) return; l->apply(p), r->apply(p); p = 0; } void pull(){ if (l) umax(s, l->s); if (r) umax(s, r->s); } bool leaf(){ return !l && !r; } }; void upd(int l, int r, ll x, int tl, int tr, pnode v){ if (l >= r) return; if (tl == l && tr == r) return void(v->apply(x)); v->push(); int tm = tl + tr >> 1; upd(l, min(tm, r), x, tl, tm, v->l); upd(max(l, tm), r, x, tm, tr, v->r); v->pull(); } ll get(int p, int tl, int tr, pnode v){ if (tl + 1 == tr) return v->s; v->push(); int tm = tl + tr >> 1; if (p < tm) return get(p, tl, tm, v->l); return get(p, tm, tr, v->r); } void mrg(pnode &v1, pnode v2){ // cout << "+\n"; if (!v1 || !v2) return void(v1 = v1 ? v1 : v2); if (v1->leaf()){ // cout << "v1 LEAF\n"; v1->s += v2->s; v1->p += v2->p; v1->l = v2->l, v1->r = v2->r; } else if (!v2->leaf()){ v1->push(), v2->push(); mrg(v1->l, v2->l), mrg(v1->r, v2->r); } else{ // cout << "v2 LEAF\n"; v1->s += v2->s; v1->p += v2->p; } delete v2; v1->pull(); } void dbg(int l, int r, pnode v){ if (!v){ for (int i = l; i < r; ++i){ cout << "0 "; } return; } if (l + 1 == r) return void(cout << v->s << " "); v->push(); int m = l + r >> 1; dbg(l, m, v->l), dbg(m, r, v->r); } inline int solve(){ int n, m, k; cin >> n >> m >> k; vec <vec <int>> g(n); for (int i = 1; i < n; ++i){ int p; cin >> p, --p; g[p].push_back(i); } vec <int> d(n, -1), w(n); for (int i = 0; i < m; ++i){ int u, x, y; cin >> u >> x >> y, --u, --x; d[u] = x, w[u] = y; } { vec <pnode> dp(n); auto dfs = [&](auto &&dfs, int u) -> void{ dp[u] = new node; for (auto &v: g[u]){ dfs(dfs, v); mrg(dp[u], dp[v]); } // cout << u + 1 << ":\n"; // cout << " Before: "; // dbg(0, k, dp[u]); // cout << "\n"; if (~d[u]){ ll nw = get(d[u], 0, k, dp[u]) + w[u]; // cout << " upd " << d[u] << " " << k - 1 << " with " << nw << "\n"; upd(d[u], k, nw, 0, k, dp[u]); } // cout << " After: "; // dbg(0, k, dp[u]); // cout << "\n"; }; dfs(dfs, 0); cout << dp[0]->s << "\n"; } // cout << "\n"; // { // vec <vec <ll>> dp(n, vec <ll> (k)); // auto dfs = [&](auto &&dfs, int u) -> void{ // for (auto &v: g[u]){ // dfs(dfs, v); // for (int i = 0; i < k; ++i){ // dp[u][i] += dp[v][i]; // } // } // cout << u + 1 << ":\n"; // cout << " Before: "; // for (int i = 0; i < k; ++i){ // cout << dp[u][i] << " "; // } // cout << "\n"; // if (~d[u]){ // ll nw = dp[u][d[u]] + w[u]; // cout << "upd " << d[u] << " " << k - 1 << " with " << nw << "\n"; // for (int i = d[u]; i < k; ++i){ // umax(dp[u][i], nw); // } // } // cout << " After: "; // for (int i = 0; i < k; ++i){ // cout << dp[u][i] << " "; // } // cout << "\n"; // }; // dfs(dfs, 0); // cout << *max_element(all(dp[0])); // }; return 0; } inline void precalc(){} signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tst = 1; //cin >> tst; precalc(); while(tst--) solve(); return 0; }

Compilation message (stderr)

magictree.cpp: In function 'void upd(int, int, ll, int, int, pnode)':
magictree.cpp:63:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
magictree.cpp: In function 'll get(int, int, int, pnode)':
magictree.cpp:72:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
magictree.cpp: In function 'void dbg(int, int, pnode)':
magictree.cpp:108:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  108 |       int m = l + r >> 1;
      |               ~~^~~
#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...