# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
531437 | 2022-02-28T17:00:03 Z | Killer2501 | Magic Tree (CEOI19_magictree) | C++17 | 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, a[N], lab[N], b[N], tong, d[N], t, c[N], dp[N], k; ll 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(auto x: mp[v])mp[u][x.fi] += x.se; } if(b[u]) { mp[u][b[u]] += a[u]; map<int, ll>:: iterator it = mp[u].upper_bound(b[u]), nxt; for(ll v = 0; it != mp[u].end(); it = nxt) { v += it->se; if(v <= a[u]) { nxt = next(it); mp[u].erase(it); } else { it->se = v-a[u]; break; } } } /* 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(auto 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 9676 KB | Output is correct |
2 | Correct | 6 ms | 9676 KB | Output is correct |
3 | Correct | 8 ms | 9720 KB | Output is correct |
4 | Correct | 5 ms | 9720 KB | Output is correct |
5 | Correct | 6 ms | 9712 KB | Output is correct |
6 | Correct | 6 ms | 9676 KB | Output is correct |
7 | Correct | 5 ms | 9804 KB | Output is correct |
8 | Correct | 5 ms | 9712 KB | Output is correct |
9 | Correct | 5 ms | 9676 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 353 ms | 129120 KB | Output is correct |
2 | Runtime error | 1946 ms | 1048580 KB | Execution killed with signal 9 |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 10060 KB | Output is correct |
2 | Correct | 9 ms | 11340 KB | Output is correct |
3 | Correct | 38 ms | 22344 KB | Output is correct |
4 | Correct | 106 ms | 62924 KB | Output is correct |
5 | Execution timed out | 2064 ms | 1005784 KB | Time limit exceeded |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 86 ms | 21632 KB | Output is correct |
2 | Correct | 83 ms | 18460 KB | Output is correct |
3 | Correct | 75 ms | 31308 KB | Output is correct |
4 | Correct | 52 ms | 22552 KB | Output is correct |
5 | Correct | 71 ms | 40668 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 9676 KB | Output is correct |
2 | Correct | 6 ms | 9676 KB | Output is correct |
3 | Correct | 8 ms | 9720 KB | Output is correct |
4 | Correct | 5 ms | 9720 KB | Output is correct |
5 | Correct | 6 ms | 9712 KB | Output is correct |
6 | Correct | 6 ms | 9676 KB | Output is correct |
7 | Correct | 5 ms | 9804 KB | Output is correct |
8 | Correct | 5 ms | 9712 KB | Output is correct |
9 | Correct | 5 ms | 9676 KB | Output is correct |
10 | Correct | 130 ms | 40456 KB | Output is correct |
11 | Correct | 114 ms | 32984 KB | Output is correct |
12 | Correct | 265 ms | 138576 KB | Output is correct |
13 | Correct | 220 ms | 124012 KB | Output is correct |
14 | Correct | 269 ms | 145960 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 11212 KB | Output is correct |
2 | Correct | 45 ms | 13860 KB | Output is correct |
3 | Correct | 36 ms | 13892 KB | Output is correct |
4 | Correct | 37 ms | 14540 KB | Output is correct |
5 | Correct | 81 ms | 42244 KB | Output is correct |
6 | Correct | 706 ms | 281296 KB | Output is correct |
7 | Correct | 684 ms | 305588 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 9676 KB | Output is correct |
2 | Correct | 6 ms | 9676 KB | Output is correct |
3 | Correct | 8 ms | 9720 KB | Output is correct |
4 | Correct | 5 ms | 9720 KB | Output is correct |
5 | Correct | 6 ms | 9712 KB | Output is correct |
6 | Correct | 6 ms | 9676 KB | Output is correct |
7 | Correct | 5 ms | 9804 KB | Output is correct |
8 | Correct | 5 ms | 9712 KB | Output is correct |
9 | Correct | 5 ms | 9676 KB | Output is correct |
10 | Correct | 6 ms | 10060 KB | Output is correct |
11 | Correct | 9 ms | 11340 KB | Output is correct |
12 | Correct | 38 ms | 22344 KB | Output is correct |
13 | Correct | 106 ms | 62924 KB | Output is correct |
14 | Execution timed out | 2064 ms | 1005784 KB | Time limit exceeded |
15 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 9676 KB | Output is correct |
2 | Correct | 6 ms | 9676 KB | Output is correct |
3 | Correct | 8 ms | 9720 KB | Output is correct |
4 | Correct | 5 ms | 9720 KB | Output is correct |
5 | Correct | 6 ms | 9712 KB | Output is correct |
6 | Correct | 6 ms | 9676 KB | Output is correct |
7 | Correct | 5 ms | 9804 KB | Output is correct |
8 | Correct | 5 ms | 9712 KB | Output is correct |
9 | Correct | 5 ms | 9676 KB | Output is correct |
10 | Correct | 353 ms | 129120 KB | Output is correct |
11 | Runtime error | 1946 ms | 1048580 KB | Execution killed with signal 9 |
12 | Halted | 0 ms | 0 KB | - |