| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 650688 |
2022-10-14T16:46:58 Z |
Tob |
Fireworks (APIO16_fireworks) |
C++14 |
|
498 ms |
113228 KB |
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
ll nxt() {ll num; cin >> num; return num;}
typedef pair <ll, ll> pii;
const int N = 300007;
int n, m;
ll nag[N];
vector <pii> adj[N];
multiset <ll> dfs(int x) {
if (adj[x].empty()) return {};
multiset <ll> s, tmp;
for (auto it : adj[x]) {
pii xx = {0, 0};
tmp = dfs(it.F);
auto p = tmp.end();
if (!tmp.empty()) --p;
ll nn = nag[it.F];
nag[x] += nn;
//MODIFY
for (int i = tmp.size(); i >= nn; i--) {
if (i == nn + 1) xx.S = *p;
if (i == nn) xx.F = *p;
p = tmp.erase(p);
if (!tmp.empty()) --p;
}
tmp.insert(xx.F + it.S);
tmp.insert(xx.S + it.S);
//COMBINE
if (s.size() < tmp.size()) swap(s, tmp);
for (auto itt : tmp) s.insert(itt);
}
return s;
}
int main () {
cin >> n >> m;
ll poc = 0, nagib = -m, res, la = 0;
for (int i = 2; i <= n+m; i++) {
ll p, c; cin >> p >> c;
poc += c;
adj[p].pb({i, c});
if (i > n) nag[i] = 1;
}
res = poc;
multiset <ll> s = dfs(1);
for (auto it : s) {
poc += nagib * (it - la);
res = min(res, poc);
nagib++;
la = it;
}
cout << res;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 8 |
Correct |
5 ms |
7292 KB |
Output is correct |
| 9 |
Correct |
5 ms |
7352 KB |
Output is correct |
| 10 |
Correct |
6 ms |
7364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 4 |
Correct |
5 ms |
7288 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7332 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 8 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 9 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 10 |
Correct |
7 ms |
7252 KB |
Output is correct |
| 11 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 12 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 13 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 14 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 15 |
Correct |
6 ms |
7352 KB |
Output is correct |
| 16 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 17 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 18 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 19 |
Correct |
4 ms |
7356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 8 |
Correct |
5 ms |
7292 KB |
Output is correct |
| 9 |
Correct |
5 ms |
7352 KB |
Output is correct |
| 10 |
Correct |
6 ms |
7364 KB |
Output is correct |
| 11 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 12 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 13 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 14 |
Correct |
5 ms |
7288 KB |
Output is correct |
| 15 |
Correct |
4 ms |
7332 KB |
Output is correct |
| 16 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 17 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 19 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 20 |
Correct |
7 ms |
7252 KB |
Output is correct |
| 21 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 22 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 23 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 24 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 25 |
Correct |
6 ms |
7352 KB |
Output is correct |
| 26 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 27 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 28 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 29 |
Correct |
4 ms |
7356 KB |
Output is correct |
| 30 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 31 |
Correct |
6 ms |
7444 KB |
Output is correct |
| 32 |
Correct |
6 ms |
7380 KB |
Output is correct |
| 33 |
Correct |
7 ms |
7440 KB |
Output is correct |
| 34 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 35 |
Correct |
11 ms |
7612 KB |
Output is correct |
| 36 |
Correct |
12 ms |
7636 KB |
Output is correct |
| 37 |
Correct |
10 ms |
7636 KB |
Output is correct |
| 38 |
Correct |
9 ms |
7624 KB |
Output is correct |
| 39 |
Correct |
9 ms |
7636 KB |
Output is correct |
| 40 |
Correct |
9 ms |
9044 KB |
Output is correct |
| 41 |
Correct |
9 ms |
9044 KB |
Output is correct |
| 42 |
Correct |
8 ms |
7636 KB |
Output is correct |
| 43 |
Correct |
10 ms |
8388 KB |
Output is correct |
| 44 |
Correct |
9 ms |
8136 KB |
Output is correct |
| 45 |
Correct |
10 ms |
8148 KB |
Output is correct |
| 46 |
Correct |
8 ms |
7748 KB |
Output is correct |
| 47 |
Correct |
9 ms |
7764 KB |
Output is correct |
| 48 |
Correct |
9 ms |
7748 KB |
Output is correct |
| 49 |
Correct |
9 ms |
7764 KB |
Output is correct |
| 50 |
Correct |
8 ms |
7716 KB |
Output is correct |
| 51 |
Correct |
9 ms |
7764 KB |
Output is correct |
| 52 |
Correct |
12 ms |
7764 KB |
Output is correct |
| 53 |
Correct |
13 ms |
7804 KB |
Output is correct |
| 54 |
Correct |
9 ms |
8008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7360 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 6 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 7 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 8 |
Correct |
5 ms |
7292 KB |
Output is correct |
| 9 |
Correct |
5 ms |
7352 KB |
Output is correct |
| 10 |
Correct |
6 ms |
7364 KB |
Output is correct |
| 11 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 12 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 13 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 14 |
Correct |
5 ms |
7288 KB |
Output is correct |
| 15 |
Correct |
4 ms |
7332 KB |
Output is correct |
| 16 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 17 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 18 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 19 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 20 |
Correct |
7 ms |
7252 KB |
Output is correct |
| 21 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 22 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 23 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 24 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 25 |
Correct |
6 ms |
7352 KB |
Output is correct |
| 26 |
Correct |
5 ms |
7356 KB |
Output is correct |
| 27 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 28 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 29 |
Correct |
4 ms |
7356 KB |
Output is correct |
| 30 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 31 |
Correct |
6 ms |
7444 KB |
Output is correct |
| 32 |
Correct |
6 ms |
7380 KB |
Output is correct |
| 33 |
Correct |
7 ms |
7440 KB |
Output is correct |
| 34 |
Correct |
7 ms |
7508 KB |
Output is correct |
| 35 |
Correct |
11 ms |
7612 KB |
Output is correct |
| 36 |
Correct |
12 ms |
7636 KB |
Output is correct |
| 37 |
Correct |
10 ms |
7636 KB |
Output is correct |
| 38 |
Correct |
9 ms |
7624 KB |
Output is correct |
| 39 |
Correct |
9 ms |
7636 KB |
Output is correct |
| 40 |
Correct |
9 ms |
9044 KB |
Output is correct |
| 41 |
Correct |
9 ms |
9044 KB |
Output is correct |
| 42 |
Correct |
8 ms |
7636 KB |
Output is correct |
| 43 |
Correct |
10 ms |
8388 KB |
Output is correct |
| 44 |
Correct |
9 ms |
8136 KB |
Output is correct |
| 45 |
Correct |
10 ms |
8148 KB |
Output is correct |
| 46 |
Correct |
8 ms |
7748 KB |
Output is correct |
| 47 |
Correct |
9 ms |
7764 KB |
Output is correct |
| 48 |
Correct |
9 ms |
7748 KB |
Output is correct |
| 49 |
Correct |
9 ms |
7764 KB |
Output is correct |
| 50 |
Correct |
8 ms |
7716 KB |
Output is correct |
| 51 |
Correct |
9 ms |
7764 KB |
Output is correct |
| 52 |
Correct |
12 ms |
7764 KB |
Output is correct |
| 53 |
Correct |
13 ms |
7804 KB |
Output is correct |
| 54 |
Correct |
9 ms |
8008 KB |
Output is correct |
| 55 |
Correct |
17 ms |
8264 KB |
Output is correct |
| 56 |
Correct |
56 ms |
10840 KB |
Output is correct |
| 57 |
Correct |
110 ms |
13264 KB |
Output is correct |
| 58 |
Correct |
150 ms |
15084 KB |
Output is correct |
| 59 |
Correct |
211 ms |
17828 KB |
Output is correct |
| 60 |
Correct |
252 ms |
19880 KB |
Output is correct |
| 61 |
Correct |
297 ms |
22144 KB |
Output is correct |
| 62 |
Correct |
310 ms |
24024 KB |
Output is correct |
| 63 |
Correct |
387 ms |
26948 KB |
Output is correct |
| 64 |
Correct |
408 ms |
27316 KB |
Output is correct |
| 65 |
Correct |
292 ms |
113144 KB |
Output is correct |
| 66 |
Correct |
305 ms |
113228 KB |
Output is correct |
| 67 |
Correct |
252 ms |
24132 KB |
Output is correct |
| 68 |
Correct |
342 ms |
73088 KB |
Output is correct |
| 69 |
Correct |
397 ms |
66396 KB |
Output is correct |
| 70 |
Correct |
383 ms |
66448 KB |
Output is correct |
| 71 |
Correct |
494 ms |
35092 KB |
Output is correct |
| 72 |
Correct |
468 ms |
34992 KB |
Output is correct |
| 73 |
Correct |
466 ms |
33820 KB |
Output is correct |
| 74 |
Correct |
401 ms |
33924 KB |
Output is correct |
| 75 |
Correct |
429 ms |
33076 KB |
Output is correct |
| 76 |
Correct |
449 ms |
33076 KB |
Output is correct |
| 77 |
Correct |
461 ms |
32760 KB |
Output is correct |
| 78 |
Correct |
498 ms |
33348 KB |
Output is correct |
| 79 |
Correct |
463 ms |
45944 KB |
Output is correct |
