# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
582550 | 2022-06-24T05:19:37 Z | 반딧불(#8370) | Magic Tree (CEOI19_magictree) | C++17 | 102 ms | 23824 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Fruit{ int v, d; ll w; Fruit(){} Fruit(int v, int d, ll w): v(v), d(d), w(w){} }; int n, m, k; int par[100002]; vector<int> child[100002]; int in[100002], out[100002], inCnt=-1; vector<pair<int, ll> > fruit[100002]; int state[100002]; Fruit arr[100002]; ll DP[1048576]; void dfs(int x){ in[x] = ++inCnt; for(auto y: child[x]) dfs(y); out[x] = inCnt; for(int i=in[x]; i<=out[x]; i++) state[x] |= (1<<i); } int main(){ scanf("%d %d %d", &n, &m, &k); for(int i=2; i<=n; i++) scanf("%d", &par[i]), child[par[i]].push_back(i); ll ans = 0; for(int i=1; i<=m; i++){ int v, d, w; scanf("%d %d %d", &v, &d, &w); fruit[d].push_back(make_pair(v, w)); arr[i] = Fruit(v, d, w); ans += w; } dfs(1); sort(arr+1, arr+m+1, [&](Fruit &a, Fruit &b){ if(a.d==b.d) return in[a.v]>in[b.v]; return a.d<b.d; }); for(int i=1; i<=m; i++){ Fruit f = arr[i]; for(int b=(1<<n)-1; b>=0; b--){ if(b & (1<<in[f.v])) continue; DP[b|state[f.v]] = max(DP[b|state[f.v]], DP[b]+f.w); } } printf("%lld", *max_element(DP, DP+(1<<n))); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4992 KB | Output is correct |
2 | Correct | 57 ms | 13124 KB | Output is correct |
3 | Correct | 32 ms | 13128 KB | Output is correct |
4 | Correct | 50 ms | 13212 KB | Output is correct |
5 | Correct | 45 ms | 9124 KB | Output is correct |
6 | Correct | 52 ms | 9008 KB | Output is correct |
7 | Correct | 48 ms | 9124 KB | Output is correct |
8 | Correct | 44 ms | 13140 KB | Output is correct |
9 | Correct | 39 ms | 13236 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 53 ms | 18220 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 9 ms | 10196 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 102 ms | 22384 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4992 KB | Output is correct |
2 | Correct | 57 ms | 13124 KB | Output is correct |
3 | Correct | 32 ms | 13128 KB | Output is correct |
4 | Correct | 50 ms | 13212 KB | Output is correct |
5 | Correct | 45 ms | 9124 KB | Output is correct |
6 | Correct | 52 ms | 9008 KB | Output is correct |
7 | Correct | 48 ms | 9124 KB | Output is correct |
8 | Correct | 44 ms | 13140 KB | Output is correct |
9 | Correct | 39 ms | 13236 KB | Output is correct |
10 | Runtime error | 80 ms | 23824 KB | Execution killed with signal 11 |
11 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 12 ms | 11356 KB | Execution killed with signal 11 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4992 KB | Output is correct |
2 | Correct | 57 ms | 13124 KB | Output is correct |
3 | Correct | 32 ms | 13128 KB | Output is correct |
4 | Correct | 50 ms | 13212 KB | Output is correct |
5 | Correct | 45 ms | 9124 KB | Output is correct |
6 | Correct | 52 ms | 9008 KB | Output is correct |
7 | Correct | 48 ms | 9124 KB | Output is correct |
8 | Correct | 44 ms | 13140 KB | Output is correct |
9 | Correct | 39 ms | 13236 KB | Output is correct |
10 | Runtime error | 9 ms | 10196 KB | Execution killed with signal 11 |
11 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4992 KB | Output is correct |
2 | Correct | 57 ms | 13124 KB | Output is correct |
3 | Correct | 32 ms | 13128 KB | Output is correct |
4 | Correct | 50 ms | 13212 KB | Output is correct |
5 | Correct | 45 ms | 9124 KB | Output is correct |
6 | Correct | 52 ms | 9008 KB | Output is correct |
7 | Correct | 48 ms | 9124 KB | Output is correct |
8 | Correct | 44 ms | 13140 KB | Output is correct |
9 | Correct | 39 ms | 13236 KB | Output is correct |
10 | Runtime error | 53 ms | 18220 KB | Execution killed with signal 11 |
11 | Halted | 0 ms | 0 KB | - |