# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
547242 | 2022-04-10T03:31:25 Z | pure_mem | Magic Tree (CEOI19_magictree) | C++14 | 106 ms | 16000 KB |
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> #define ll long long #define ld long double #define X first #define Y second #define MP make_pair using namespace std; const int N = 1e5 + 2; const int INF = 1e9; typedef map<ll, int> DP; void merge(DP& oth, DP& cur) { if(cur.size() < oth.size()) cur.swap(oth); for(auto [pos, val]: oth) { cur[pos] += val; } oth.clear(); } void insert(DP& cur, int pos, ll val) { cur[pos] += val; DP::iterator it = cur.upper_bound(pos); ll sum = 0; while(it != cur.end()) { if(it->second + sum > val) { it->second += sum - val; break; } else { sum += it->second; it = cur.erase(it); } } } int n, m, k; DP dp[N]; vector<int> g[N]; pair<int, int> fruit[N]; void dfs(int v) { for(int to: g[v]) { dfs(to); merge(dp[to], dp[v]); } insert(dp[v], fruit[v].X, fruit[v].Y); } int main () { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> k; for(int i = 2, v;i <= n;i++) { cin >> v; g[v].push_back(i); } ll all = 0; for(int i = 1;i <= m;i++) { int v, d, w; cin >> v >> d >> w; fruit[v] = {d, w}; all += w; } dfs(1); ll res = 0; for(auto [pos, val]: dp[1]) res += val; cout << all; //cout << res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 7252 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 78 ms | 11440 KB | Output is correct |
2 | Correct | 46 ms | 14180 KB | Output is correct |
3 | Correct | 106 ms | 16000 KB | Output is correct |
4 | Correct | 65 ms | 14424 KB | Output is correct |
5 | Correct | 88 ms | 15208 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 7380 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 87 ms | 9744 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 7252 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 9 ms | 7808 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 7252 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 7252 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |