Submission #956720

#TimeUsernameProblemLanguageResultExecution timeMemory
956720thangdz2k7Magic Tree (CEOI19_magictree)C++17
100 / 100
118 ms41744 KiB
// author : HuuHung // 25.3.2024 #include <bits/stdc++.h> #define ii pair <int, int> #define F first #define S second #define ll long long #define lb long double #define pb push_back #define vi vector <int> #define vll vector <ll> #define Bit(x, i) ((x) >> (i) & 1) #define Mask(i) (1ll << (i)) #define All(v) (v).begin(), (v).end() using namespace std; void maxzi(int &a, int b){ a = max(a, b); } void minzi(int &a, int b){ a = min(a, b); } const int N = 2e5 + 5; const int mod = 1e9 + 7; const int LG = 20; void add(int &a, int b){ a += b; if (a >= mod) a -= mod; if (a < 0) a += mod; } int Pow(int a, int b){ if (b == 0) return 1; if (b % 2) return 1ll * a * Pow(a, b - 1) % mod; int c = Pow(a, b / 2); return 1ll * c * c % mod; } // * end int n, m, k; int d[N], w[N]; vector <int> adj[N]; map <int, ll> dp[N]; void dfs(int u){ for (int v : adj[u]){ dfs(v); if (dp[u].size() < dp[v].size()) swap(dp[u], dp[v]); for (auto x : dp[v]) dp[u][x.F] += x.S; } if (d[u]){ dp[u][d[u]] += w[u]; while (true){ auto t = dp[u].upper_bound(d[u]); if (t == dp[u].end()) break; if (t -> S > w[u]){ t -> S -= w[u]; break; } w[u] -= t -> S; dp[u].erase(t); } } } void solve(){ cin >> n >> m >> k; for (int i = 2, p; i <= n; ++ i){ cin >> p; adj[p].pb(i); } for (int i = 1, v; i <= m; ++ i){ cin >> v; cin >> d[v] >> w[v]; } dfs(1); ll ans = 0; for (auto v : dp[1]) ans += v.S; cout << ans; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; while (t --) 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...