| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 392320 | 2021-04-20T19:22:16 Z | MiricaMatei | Worst Reporter 4 (JOI21_worst_reporter4) | C++14 | 417 ms | 81492 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int inf = 2000000000;
struct slope_trick {
map<int, long long> delta;
slope_trick () {
delta = map<int, long long>();
}
void mergeDelta(slope_trick other) {
for (auto it:other.delta)
delta[it.first] += it.second;
other.delta.clear();
}
void add(int x, long long val) {
delta[-inf] += val;
delta[x] -= val;
delta[x + 1] += val;
map<int, long long>::iterator it1, it2;
it1 = delta.lower_bound(x);
val = delta[x];
while (val < 0) {
it2 = it1;
it1--;
delta.erase(it2);
val = it1->second + val;
it1->second = val;
}
}
int mapSize() {
return delta.size();
}
long long query() {
return delta[-inf];
}
};
vector<int>G[MAXN];
int a[MAXN], h[MAXN], c[MAXN];
slope_trick dfs(int node) {
slope_trick ans;
for (auto it:G[node]) {
slope_trick aux = dfs(it);
if (aux.mapSize() > ans.mapSize())
swap(ans, aux);
ans.mergeDelta(aux);
}
ans.add(h[node], c[node]);
return ans;
}
long long solve(int node) {
slope_trick ans = dfs(node);
return ans.query();
}
int main() {
//freopen("date.in", "r", stdin);
//freopen("date.out", "w", stdout);
int N;
scanf("%d", &N);
for (int i = 1; i <= N; ++i) {
scanf("%d%d%d", &a[i], &h[i], &c[i]);
if (i > 1)
G[a[i]].push_back(i);
}
long long ans = solve(1);
printf("%lld\n", ans);
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 4940 KB | Output is correct |
| 2 | Correct | 3 ms | 4940 KB | Output is correct |
| 3 | Correct | 3 ms | 4940 KB | Output is correct |
| 4 | Correct | 4 ms | 4940 KB | Output is correct |
| 5 | Correct | 10 ms | 5544 KB | Output is correct |
| 6 | Correct | 8 ms | 5296 KB | Output is correct |
| 7 | Correct | 10 ms | 5192 KB | Output is correct |
| 8 | Correct | 11 ms | 5580 KB | Output is correct |
| 9 | Correct | 8 ms | 5196 KB | Output is correct |
| 10 | Correct | 7 ms | 5196 KB | Output is correct |
| 11 | Correct | 7 ms | 5196 KB | Output is correct |
| 12 | Correct | 8 ms | 6604 KB | Output is correct |
| 13 | Correct | 9 ms | 6476 KB | Output is correct |
| 14 | Correct | 8 ms | 5964 KB | Output is correct |
| 15 | Correct | 8 ms | 5964 KB | Output is correct |
| 16 | Correct | 13 ms | 5620 KB | Output is correct |
| 17 | Correct | 8 ms | 5196 KB | Output is correct |
| 18 | Correct | 8 ms | 5260 KB | Output is correct |
| 19 | Correct | 10 ms | 5964 KB | Output is correct |
| 20 | Correct | 8 ms | 5964 KB | Output is correct |
| 21 | Correct | 8 ms | 5856 KB | Output is correct |
| 22 | Correct | 9 ms | 5452 KB | Output is correct |
| 23 | Correct | 6 ms | 5196 KB | Output is correct |
| 24 | Correct | 8 ms | 5964 KB | Output is correct |
| 25 | Correct | 7 ms | 5904 KB | Output is correct |
| 26 | Correct | 10 ms | 6892 KB | Output is correct |
| 27 | Correct | 8 ms | 5964 KB | Output is correct |
| 28 | Correct | 8 ms | 6164 KB | Output is correct |
| 29 | Correct | 11 ms | 6500 KB | Output is correct |
| 30 | Correct | 11 ms | 6536 KB | Output is correct |
| 31 | Correct | 11 ms | 6476 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 9 ms | 5324 KB | Output is correct |
| 2 | Correct | 417 ms | 30744 KB | Output is correct |
| 3 | Correct | 265 ms | 16028 KB | Output is correct |
| 4 | Correct | 403 ms | 26812 KB | Output is correct |
| 5 | Correct | 266 ms | 15940 KB | Output is correct |
| 6 | Correct | 183 ms | 15680 KB | Output is correct |
| 7 | Correct | 186 ms | 15376 KB | Output is correct |
| 8 | Correct | 252 ms | 68932 KB | Output is correct |
| 9 | Correct | 262 ms | 68764 KB | Output is correct |
| 10 | Correct | 140 ms | 68816 KB | Output is correct |
| 11 | Correct | 205 ms | 43928 KB | Output is correct |
| 12 | Correct | 231 ms | 43856 KB | Output is correct |
| 13 | Correct | 401 ms | 30916 KB | Output is correct |
| 14 | Correct | 299 ms | 15860 KB | Output is correct |
| 15 | Correct | 125 ms | 15464 KB | Output is correct |
| 16 | Correct | 302 ms | 47428 KB | Output is correct |
| 17 | Correct | 175 ms | 40468 KB | Output is correct |
| 18 | Correct | 133 ms | 40504 KB | Output is correct |
| 19 | Correct | 252 ms | 24892 KB | Output is correct |
| 20 | Correct | 138 ms | 12472 KB | Output is correct |
| 21 | Correct | 298 ms | 48108 KB | Output is correct |
| 22 | Correct | 169 ms | 41040 KB | Output is correct |
| 23 | Correct | 316 ms | 81492 KB | Output is correct |
| 24 | Correct | 234 ms | 49024 KB | Output is correct |
| 25 | Correct | 234 ms | 63548 KB | Output is correct |
| 26 | Correct | 295 ms | 69972 KB | Output is correct |
| 27 | Correct | 299 ms | 68068 KB | Output is correct |
| 28 | Correct | 317 ms | 67972 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 3 ms | 4940 KB | Output is correct |
| 2 | Correct | 3 ms | 4940 KB | Output is correct |
| 3 | Correct | 3 ms | 4940 KB | Output is correct |
| 4 | Correct | 4 ms | 4940 KB | Output is correct |
| 5 | Correct | 10 ms | 5544 KB | Output is correct |
| 6 | Correct | 8 ms | 5296 KB | Output is correct |
| 7 | Correct | 10 ms | 5192 KB | Output is correct |
| 8 | Correct | 11 ms | 5580 KB | Output is correct |
| 9 | Correct | 8 ms | 5196 KB | Output is correct |
| 10 | Correct | 7 ms | 5196 KB | Output is correct |
| 11 | Correct | 7 ms | 5196 KB | Output is correct |
| 12 | Correct | 8 ms | 6604 KB | Output is correct |
| 13 | Correct | 9 ms | 6476 KB | Output is correct |
| 14 | Correct | 8 ms | 5964 KB | Output is correct |
| 15 | Correct | 8 ms | 5964 KB | Output is correct |
| 16 | Correct | 13 ms | 5620 KB | Output is correct |
| 17 | Correct | 8 ms | 5196 KB | Output is correct |
| 18 | Correct | 8 ms | 5260 KB | Output is correct |
| 19 | Correct | 10 ms | 5964 KB | Output is correct |
| 20 | Correct | 8 ms | 5964 KB | Output is correct |
| 21 | Correct | 8 ms | 5856 KB | Output is correct |
| 22 | Correct | 9 ms | 5452 KB | Output is correct |
| 23 | Correct | 6 ms | 5196 KB | Output is correct |
| 24 | Correct | 8 ms | 5964 KB | Output is correct |
| 25 | Correct | 7 ms | 5904 KB | Output is correct |
| 26 | Correct | 10 ms | 6892 KB | Output is correct |
| 27 | Correct | 8 ms | 5964 KB | Output is correct |
| 28 | Correct | 8 ms | 6164 KB | Output is correct |
| 29 | Correct | 11 ms | 6500 KB | Output is correct |
| 30 | Correct | 11 ms | 6536 KB | Output is correct |
| 31 | Correct | 11 ms | 6476 KB | Output is correct |
| 32 | Correct | 9 ms | 5324 KB | Output is correct |
| 33 | Correct | 417 ms | 30744 KB | Output is correct |
| 34 | Correct | 265 ms | 16028 KB | Output is correct |
| 35 | Correct | 403 ms | 26812 KB | Output is correct |
| 36 | Correct | 266 ms | 15940 KB | Output is correct |
| 37 | Correct | 183 ms | 15680 KB | Output is correct |
| 38 | Correct | 186 ms | 15376 KB | Output is correct |
| 39 | Correct | 252 ms | 68932 KB | Output is correct |
| 40 | Correct | 262 ms | 68764 KB | Output is correct |
| 41 | Correct | 140 ms | 68816 KB | Output is correct |
| 42 | Correct | 205 ms | 43928 KB | Output is correct |
| 43 | Correct | 231 ms | 43856 KB | Output is correct |
| 44 | Correct | 401 ms | 30916 KB | Output is correct |
| 45 | Correct | 299 ms | 15860 KB | Output is correct |
| 46 | Correct | 125 ms | 15464 KB | Output is correct |
| 47 | Correct | 302 ms | 47428 KB | Output is correct |
| 48 | Correct | 175 ms | 40468 KB | Output is correct |
| 49 | Correct | 133 ms | 40504 KB | Output is correct |
| 50 | Correct | 252 ms | 24892 KB | Output is correct |
| 51 | Correct | 138 ms | 12472 KB | Output is correct |
| 52 | Correct | 298 ms | 48108 KB | Output is correct |
| 53 | Correct | 169 ms | 41040 KB | Output is correct |
| 54 | Correct | 316 ms | 81492 KB | Output is correct |
| 55 | Correct | 234 ms | 49024 KB | Output is correct |
| 56 | Correct | 234 ms | 63548 KB | Output is correct |
| 57 | Correct | 295 ms | 69972 KB | Output is correct |
| 58 | Correct | 299 ms | 68068 KB | Output is correct |
| 59 | Correct | 317 ms | 67972 KB | Output is correct |
| 60 | Correct | 4 ms | 4940 KB | Output is correct |
| 61 | Incorrect | 4 ms | 5004 KB | Output isn't correct |
| 62 | Halted | 0 ms | 0 KB | - |