# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
208169 | 2020-03-10T06:55:31 Z | E869120 | Magic Tree (CEOI19_magictree) | C++14 | 2000 ms | 797304 KB |
#include <iostream> #include <vector> #include <algorithm> using namespace std; #pragma warning (disable: 4996) long long N, P[1 << 18], idx[1 << 18]; long long M, A[1 << 18], B[1 << 18], C[1 << 18]; long long K; long long dp[100009][1009]; vector<int> X[100009], Y; int main() { scanf("%lld%lld%lld", &N, &M, &K); for (int i = 2; i <= N; i++) scanf("%lld", &P[i]); for (int i = 1; i <= M; i++) scanf("%lld%lld%lld", &A[i], &B[i], &C[i]); for (int i = 2; i <= N; i++) X[P[i]].push_back(i); for (int i = 1; i <= M; i++) Y.push_back(B[i]); sort(Y.begin(), Y.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end()); for (int i = 1; i <= M; i++) B[i] = (lower_bound(Y.begin(), Y.end(), B[i]) - Y.begin()) + 1; for (int i = 1; i <= M; i++) idx[A[i]] = i; for (int i = N; i >= 1; i--) { for (int j : X[i]) { for (int k = 0; k <= Y.size(); k++) dp[i][k] += dp[j][k]; } if (idx[i] >= 1) { int id = idx[i]; dp[i][B[id]] += C[id]; } for (int j = 1; j <= Y.size(); j++) dp[i][j] = max(dp[i][j], dp[i][j - 1]); } cout << dp[1][Y.size()] << endl; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2808 KB | Output is correct |
2 | Correct | 6 ms | 2808 KB | Output is correct |
3 | Correct | 6 ms | 2808 KB | Output is correct |
4 | Correct | 6 ms | 2808 KB | Output is correct |
5 | Correct | 6 ms | 2808 KB | Output is correct |
6 | Correct | 6 ms | 2808 KB | Output is correct |
7 | Correct | 6 ms | 2808 KB | Output is correct |
8 | Correct | 7 ms | 2808 KB | Output is correct |
9 | Correct | 6 ms | 2808 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2080 ms | 179496 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 9848 KB | Output is correct |
2 | Correct | 13 ms | 9976 KB | Output is correct |
3 | Correct | 12 ms | 9848 KB | Output is correct |
4 | Execution timed out | 2094 ms | 64856 KB | Time limit exceeded |
5 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 260 ms | 412016 KB | Output is correct |
2 | Correct | 246 ms | 411884 KB | Output is correct |
3 | Correct | 241 ms | 413736 KB | Output is correct |
4 | Correct | 244 ms | 410992 KB | Output is correct |
5 | Correct | 228 ms | 414448 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2808 KB | Output is correct |
2 | Correct | 6 ms | 2808 KB | Output is correct |
3 | Correct | 6 ms | 2808 KB | Output is correct |
4 | Correct | 6 ms | 2808 KB | Output is correct |
5 | Correct | 6 ms | 2808 KB | Output is correct |
6 | Correct | 6 ms | 2808 KB | Output is correct |
7 | Correct | 6 ms | 2808 KB | Output is correct |
8 | Correct | 7 ms | 2808 KB | Output is correct |
9 | Correct | 6 ms | 2808 KB | Output is correct |
10 | Correct | 282 ms | 426608 KB | Output is correct |
11 | Correct | 282 ms | 418800 KB | Output is correct |
12 | Correct | 258 ms | 427884 KB | Output is correct |
13 | Correct | 263 ms | 424688 KB | Output is correct |
14 | Correct | 244 ms | 428660 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 193 ms | 161528 KB | Output is correct |
2 | Correct | 882 ms | 796408 KB | Output is correct |
3 | Correct | 884 ms | 796280 KB | Output is correct |
4 | Correct | 987 ms | 796360 KB | Output is correct |
5 | Correct | 992 ms | 794992 KB | Output is correct |
6 | Correct | 965 ms | 796024 KB | Output is correct |
7 | Correct | 884 ms | 797304 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2808 KB | Output is correct |
2 | Correct | 6 ms | 2808 KB | Output is correct |
3 | Correct | 6 ms | 2808 KB | Output is correct |
4 | Correct | 6 ms | 2808 KB | Output is correct |
5 | Correct | 6 ms | 2808 KB | Output is correct |
6 | Correct | 6 ms | 2808 KB | Output is correct |
7 | Correct | 6 ms | 2808 KB | Output is correct |
8 | Correct | 7 ms | 2808 KB | Output is correct |
9 | Correct | 6 ms | 2808 KB | Output is correct |
10 | Correct | 12 ms | 9848 KB | Output is correct |
11 | Correct | 13 ms | 9976 KB | Output is correct |
12 | Correct | 12 ms | 9848 KB | Output is correct |
13 | Execution timed out | 2094 ms | 64856 KB | Time limit exceeded |
14 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 2808 KB | Output is correct |
2 | Correct | 6 ms | 2808 KB | Output is correct |
3 | Correct | 6 ms | 2808 KB | Output is correct |
4 | Correct | 6 ms | 2808 KB | Output is correct |
5 | Correct | 6 ms | 2808 KB | Output is correct |
6 | Correct | 6 ms | 2808 KB | Output is correct |
7 | Correct | 6 ms | 2808 KB | Output is correct |
8 | Correct | 7 ms | 2808 KB | Output is correct |
9 | Correct | 6 ms | 2808 KB | Output is correct |
10 | Execution timed out | 2080 ms | 179496 KB | Time limit exceeded |
11 | Halted | 0 ms | 0 KB | - |