# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
531697 | 2022-03-01T09:57:03 Z | Yazan_Alattar | Magic Tree (CEOI19_magictree) | C++14 | 2000 ms | 797812 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define F first #define S second #define pb push_back #define endl "\n" #define all(x) x.begin(), x.end() const int M = 100007; const ll inf = 1e18; const ll mod = 998244353; const double pi = acos(-1); const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0}; const int block = 320; vector <int> adj[M]; int n, m, k, ripe[M], w[M], vert[M]; ll dp[M][1007]; void dfs(int node){ for(auto i : adj[node]){ dfs(i); for(int j = 1; j <= k; ++j) dp[node][j] += dp[i][j]; } dp[node][ripe[node]] += w[node]; for(int i = 1; i <= k; ++i) dp[node][i] = max(dp[node][i], dp[node][i - 1]); return; } int main(){ scanf("%d%d%d", &n, &m, &k); k = min(k, m); for(int i = 2; i <= n; ++i){ int p; scanf("%d", &p); adj[p].pb(i); } vector <int> v; for(int i = 1; i <= m; ++i){ scanf("%d", &vert[i]); scanf("%d%d", &ripe[vert[i]], &w[vert[i]]); v.pb(ripe[vert[i]]); } sort(all(v)); v.erase(unique(all(v)), v.end()); for(int i = 1; i <= m; ++i) for(int j = 0; j < (int)v.size(); ++j) if(v[j] == ripe[vert[i]]){ripe[vert[i]] = j + 1; break;} dfs(1); printf("%lld\n", dp[1][k]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2644 KB | Output is correct |
2 | Correct | 2 ms | 2636 KB | Output is correct |
3 | Correct | 1 ms | 2636 KB | Output is correct |
4 | Correct | 1 ms | 2636 KB | Output is correct |
5 | Correct | 2 ms | 2648 KB | Output is correct |
6 | Correct | 2 ms | 2636 KB | Output is correct |
7 | Correct | 2 ms | 2636 KB | Output is correct |
8 | Correct | 2 ms | 2636 KB | Output is correct |
9 | Correct | 2 ms | 2652 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2093 ms | 782796 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 10572 KB | Output is correct |
2 | Correct | 8 ms | 10592 KB | Output is correct |
3 | Correct | 7 ms | 10572 KB | Output is correct |
4 | Execution timed out | 2069 ms | 33048 KB | Time limit exceeded |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 238 ms | 410328 KB | Output is correct |
2 | Correct | 223 ms | 409548 KB | Output is correct |
3 | Correct | 231 ms | 414488 KB | Output is correct |
4 | Correct | 193 ms | 408732 KB | Output is correct |
5 | Correct | 225 ms | 419716 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2644 KB | Output is correct |
2 | Correct | 2 ms | 2636 KB | Output is correct |
3 | Correct | 1 ms | 2636 KB | Output is correct |
4 | Correct | 1 ms | 2636 KB | Output is correct |
5 | Correct | 2 ms | 2648 KB | Output is correct |
6 | Correct | 2 ms | 2636 KB | Output is correct |
7 | Correct | 2 ms | 2636 KB | Output is correct |
8 | Correct | 2 ms | 2636 KB | Output is correct |
9 | Correct | 2 ms | 2652 KB | Output is correct |
10 | Correct | 248 ms | 423804 KB | Output is correct |
11 | Correct | 273 ms | 415804 KB | Output is correct |
12 | Correct | 229 ms | 427788 KB | Output is correct |
13 | Correct | 206 ms | 422124 KB | Output is correct |
14 | Correct | 212 ms | 433088 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 160 ms | 160892 KB | Output is correct |
2 | Correct | 700 ms | 793836 KB | Output is correct |
3 | Correct | 733 ms | 793856 KB | Output is correct |
4 | Correct | 832 ms | 793780 KB | Output is correct |
5 | Correct | 849 ms | 792460 KB | Output is correct |
6 | Correct | 809 ms | 795188 KB | Output is correct |
7 | Correct | 752 ms | 797812 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2644 KB | Output is correct |
2 | Correct | 2 ms | 2636 KB | Output is correct |
3 | Correct | 1 ms | 2636 KB | Output is correct |
4 | Correct | 1 ms | 2636 KB | Output is correct |
5 | Correct | 2 ms | 2648 KB | Output is correct |
6 | Correct | 2 ms | 2636 KB | Output is correct |
7 | Correct | 2 ms | 2636 KB | Output is correct |
8 | Correct | 2 ms | 2636 KB | Output is correct |
9 | Correct | 2 ms | 2652 KB | Output is correct |
10 | Correct | 8 ms | 10572 KB | Output is correct |
11 | Correct | 8 ms | 10592 KB | Output is correct |
12 | Correct | 7 ms | 10572 KB | Output is correct |
13 | Execution timed out | 2069 ms | 33048 KB | Time limit exceeded |
14 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2644 KB | Output is correct |
2 | Correct | 2 ms | 2636 KB | Output is correct |
3 | Correct | 1 ms | 2636 KB | Output is correct |
4 | Correct | 1 ms | 2636 KB | Output is correct |
5 | Correct | 2 ms | 2648 KB | Output is correct |
6 | Correct | 2 ms | 2636 KB | Output is correct |
7 | Correct | 2 ms | 2636 KB | Output is correct |
8 | Correct | 2 ms | 2636 KB | Output is correct |
9 | Correct | 2 ms | 2652 KB | Output is correct |
10 | Execution timed out | 2093 ms | 782796 KB | Time limit exceeded |
11 | Halted | 0 ms | 0 KB | - |