# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
531424 | 2022-02-28T16:43:06 Z | Killer2501 | Magic Tree (CEOI19_magictree) | C++14 | 2000 ms | 1048580 KB |
#include <bits/stdc++.h> #define ll long long #define ld long double #define ull unsigned long long #define pb push_back #define pll pair<ll, ll> #define pii pair<int, ll> #define fi first #define se second using namespace std; const int N = 1e5+5; const int M = 250; const int mod = 1e9+7; const ll base = 75; const ll inf = 1e16; int n, m, lab[N], b[N], tong, d[N], t, c[N], dp[N], k; ll a[N], ans; vector<int> adj[N], radj[N]; vector<pll> vi; string s; map<int, ll> mp[N]; void dfs(int u) { for(int v: adj[u]) { dfs(v); if(mp[v].empty())continue; if(mp[u].size() > mp[v].size())swap(mp[u], mp[v]); for(pii x: mp[v])mp[u][x.fi] += x.se; } if(b[u]) { ll t = a[u]; while(true) { auto it = mp[u].upper_bound(b[u]); if(it == mp[u].end())break; if(t >= (*it).se) { t -= (*it).se; mp[u].erase(it); } else { mp[u][(*it).fi] -= t; break; } } mp[u][b[u]] += a[u]; } /* cout << u << " "<<b[u]<<" "<<a[u]<< '\n'; for(auto x: mp[u])cout << x.fi <<" "<<x.se<<'\n'; */ } void sol() { cin >> n >> m >> k; for(int i = 2; i <= n; i ++) { cin >> t; adj[t].pb(i); } for(int i = 1; i <= m; i ++) { cin >> t; cin >> b[t] >> a[t]; } dfs(1); if(!mp[1].empty())for(pii x: mp[1])ans += x.se; cout << ans; } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); #define task "test" if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int test = 1; //cin >> test; while(test -- > 0)sol(); return 0; } /* 1234 21 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 9676 KB | Output is correct |
2 | Correct | 6 ms | 9676 KB | Output is correct |
3 | Correct | 5 ms | 9612 KB | Output is correct |
4 | Correct | 5 ms | 9676 KB | Output is correct |
5 | Correct | 5 ms | 9676 KB | Output is correct |
6 | Correct | 5 ms | 9732 KB | Output is correct |
7 | Correct | 5 ms | 9676 KB | Output is correct |
8 | Correct | 5 ms | 9676 KB | Output is correct |
9 | Correct | 5 ms | 9676 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 334 ms | 129368 KB | Output is correct |
2 | Runtime error | 1873 ms | 1048580 KB | Execution killed with signal 9 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 9992 KB | Output is correct |
2 | Correct | 8 ms | 11340 KB | Output is correct |
3 | Correct | 33 ms | 22336 KB | Output is correct |
4 | Correct | 97 ms | 62200 KB | Output is correct |
5 | Execution timed out | 2116 ms | 1048580 KB | Time limit exceeded |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 95 ms | 21600 KB | Output is correct |
2 | Correct | 77 ms | 18400 KB | Output is correct |
3 | Correct | 63 ms | 31168 KB | Output is correct |
4 | Correct | 45 ms | 22444 KB | Output is correct |
5 | Correct | 58 ms | 40568 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 9676 KB | Output is correct |
2 | Correct | 6 ms | 9676 KB | Output is correct |
3 | Correct | 5 ms | 9612 KB | Output is correct |
4 | Correct | 5 ms | 9676 KB | Output is correct |
5 | Correct | 5 ms | 9676 KB | Output is correct |
6 | Correct | 5 ms | 9732 KB | Output is correct |
7 | Correct | 5 ms | 9676 KB | Output is correct |
8 | Correct | 5 ms | 9676 KB | Output is correct |
9 | Correct | 5 ms | 9676 KB | Output is correct |
10 | Correct | 127 ms | 40340 KB | Output is correct |
11 | Correct | 114 ms | 32840 KB | Output is correct |
12 | Correct | 263 ms | 138444 KB | Output is correct |
13 | Correct | 219 ms | 124000 KB | Output is correct |
14 | Correct | 244 ms | 145888 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 11212 KB | Output is correct |
2 | Correct | 31 ms | 13820 KB | Output is correct |
3 | Correct | 31 ms | 13900 KB | Output is correct |
4 | Correct | 34 ms | 14472 KB | Output is correct |
5 | Correct | 76 ms | 42376 KB | Output is correct |
6 | Correct | 695 ms | 281388 KB | Output is correct |
7 | Correct | 634 ms | 305576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 9676 KB | Output is correct |
2 | Correct | 6 ms | 9676 KB | Output is correct |
3 | Correct | 5 ms | 9612 KB | Output is correct |
4 | Correct | 5 ms | 9676 KB | Output is correct |
5 | Correct | 5 ms | 9676 KB | Output is correct |
6 | Correct | 5 ms | 9732 KB | Output is correct |
7 | Correct | 5 ms | 9676 KB | Output is correct |
8 | Correct | 5 ms | 9676 KB | Output is correct |
9 | Correct | 5 ms | 9676 KB | Output is correct |
10 | Correct | 6 ms | 9992 KB | Output is correct |
11 | Correct | 8 ms | 11340 KB | Output is correct |
12 | Correct | 33 ms | 22336 KB | Output is correct |
13 | Correct | 97 ms | 62200 KB | Output is correct |
14 | Execution timed out | 2116 ms | 1048580 KB | Time limit exceeded |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 9676 KB | Output is correct |
2 | Correct | 6 ms | 9676 KB | Output is correct |
3 | Correct | 5 ms | 9612 KB | Output is correct |
4 | Correct | 5 ms | 9676 KB | Output is correct |
5 | Correct | 5 ms | 9676 KB | Output is correct |
6 | Correct | 5 ms | 9732 KB | Output is correct |
7 | Correct | 5 ms | 9676 KB | Output is correct |
8 | Correct | 5 ms | 9676 KB | Output is correct |
9 | Correct | 5 ms | 9676 KB | Output is correct |
10 | Correct | 334 ms | 129368 KB | Output is correct |
11 | Runtime error | 1873 ms | 1048580 KB | Execution killed with signal 9 |
12 | Halted | 0 ms | 0 KB | - |