| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 392329 | 2021-04-20T19:53:40 Z | MiricaMatei | Worst Reporter 4 (JOI21_worst_reporter4) | C++14 | 452 ms | 77156 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int inf = 2000000000;
const long long INF = 1000000000000000000LL;
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;
}
void level(int x) {
map<int, long long>::iterator it1, it2;
it1 = delta.lower_bound(x);
long long 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];
bool vis[MAXN], visc[MAXN];
slope_trick dfs(int node) {
slope_trick ans;
vis[node] = 1;
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]);
ans.level(h[node]);
return ans;
}
long long solve(int node) {
vector<int>cycle;
while (!vis[node]) {
vis[node] = 1;
node = a[node];
}
while (!visc[node]) {
cycle.push_back(node);
visc[node] = 1;
node = a[node];
}
slope_trick ans;
for (auto it:cycle)
for (auto son:G[it])
if (!visc[son]) {
slope_trick aux = dfs(son);
if (aux.mapSize() > ans.mapSize())
swap(ans, aux);
ans.mergeDelta(aux);
}
for (auto it:cycle) {
vis[it] = 1;
ans.add(h[it], c[it]);
}
long long sol = INF;
long long s = 0;
for (auto it:ans.delta) {
s += it.second;
sol = min(sol, s);
}
return sol;
}
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]);
G[a[i]].push_back(i);
}
long long ans = 0;
for (int i = 1; i <= N; ++i)
if (!vis[i])
ans += solve(i);
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 | 3 ms | 4940 KB | Output is correct |
| 5 | Correct | 10 ms | 5528 KB | Output is correct |
| 6 | Correct | 8 ms | 5268 KB | Output is correct |
| 7 | Correct | 7 ms | 5196 KB | Output is correct |
| 8 | Correct | 10 ms | 5580 KB | Output is correct |
| 9 | Correct | 10 ms | 5264 KB | Output is correct |
| 10 | Correct | 9 ms | 5272 KB | Output is correct |
| 11 | Correct | 8 ms | 5272 KB | Output is correct |
| 12 | Correct | 9 ms | 6604 KB | Output is correct |
| 13 | Correct | 7 ms | 6604 KB | Output is correct |
| 14 | Correct | 8 ms | 5964 KB | Output is correct |
| 15 | Correct | 7 ms | 5964 KB | Output is correct |
| 16 | Correct | 10 ms | 5580 KB | Output is correct |
| 17 | Correct | 11 ms | 5268 KB | Output is correct |
| 18 | Correct | 6 ms | 5272 KB | Output is correct |
| 19 | Correct | 8 ms | 5964 KB | Output is correct |
| 20 | Correct | 7 ms | 5836 KB | Output is correct |
| 21 | Correct | 7 ms | 5780 KB | Output is correct |
| 22 | Correct | 8 ms | 5524 KB | Output is correct |
| 23 | Correct | 6 ms | 5196 KB | Output is correct |
| 24 | Correct | 9 ms | 6092 KB | Output is correct |
| 25 | Correct | 7 ms | 6036 KB | Output is correct |
| 26 | Correct | 9 ms | 6884 KB | Output is correct |
| 27 | Correct | 8 ms | 5908 KB | Output is correct |
| 28 | Correct | 11 ms | 6160 KB | Output is correct |
| 29 | Correct | 9 ms | 6552 KB | Output is correct |
| 30 | Correct | 9 ms | 6476 KB | Output is correct |
| 31 | Correct | 9 ms | 6464 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 5452 KB | Output is correct |
| 2 | Correct | 394 ms | 27020 KB | Output is correct |
| 3 | Correct | 276 ms | 12112 KB | Output is correct |
| 4 | Correct | 377 ms | 22980 KB | Output is correct |
| 5 | Correct | 296 ms | 12076 KB | Output is correct |
| 6 | Correct | 242 ms | 11772 KB | Output is correct |
| 7 | Correct | 171 ms | 11772 KB | Output is correct |
| 8 | Correct | 215 ms | 65076 KB | Output is correct |
| 9 | Correct | 205 ms | 64904 KB | Output is correct |
| 10 | Correct | 178 ms | 64764 KB | Output is correct |
| 11 | Correct | 204 ms | 40020 KB | Output is correct |
| 12 | Correct | 234 ms | 39876 KB | Output is correct |
| 13 | Correct | 452 ms | 27076 KB | Output is correct |
| 14 | Correct | 259 ms | 12012 KB | Output is correct |
| 15 | Correct | 121 ms | 11588 KB | Output is correct |
| 16 | Correct | 297 ms | 43672 KB | Output is correct |
| 17 | Correct | 171 ms | 36736 KB | Output is correct |
| 18 | Correct | 133 ms | 36636 KB | Output is correct |
| 19 | Correct | 284 ms | 21728 KB | Output is correct |
| 20 | Correct | 132 ms | 9336 KB | Output is correct |
| 21 | Correct | 304 ms | 44220 KB | Output is correct |
| 22 | Correct | 169 ms | 37188 KB | Output is correct |
| 23 | Correct | 286 ms | 77156 KB | Output is correct |
| 24 | Correct | 257 ms | 45832 KB | Output is correct |
| 25 | Correct | 238 ms | 60360 KB | Output is correct |
| 26 | Correct | 241 ms | 66804 KB | Output is correct |
| 27 | Correct | 283 ms | 64648 KB | Output is correct |
| 28 | Correct | 290 ms | 64764 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 | 3 ms | 4940 KB | Output is correct |
| 5 | Correct | 10 ms | 5528 KB | Output is correct |
| 6 | Correct | 8 ms | 5268 KB | Output is correct |
| 7 | Correct | 7 ms | 5196 KB | Output is correct |
| 8 | Correct | 10 ms | 5580 KB | Output is correct |
| 9 | Correct | 10 ms | 5264 KB | Output is correct |
| 10 | Correct | 9 ms | 5272 KB | Output is correct |
| 11 | Correct | 8 ms | 5272 KB | Output is correct |
| 12 | Correct | 9 ms | 6604 KB | Output is correct |
| 13 | Correct | 7 ms | 6604 KB | Output is correct |
| 14 | Correct | 8 ms | 5964 KB | Output is correct |
| 15 | Correct | 7 ms | 5964 KB | Output is correct |
| 16 | Correct | 10 ms | 5580 KB | Output is correct |
| 17 | Correct | 11 ms | 5268 KB | Output is correct |
| 18 | Correct | 6 ms | 5272 KB | Output is correct |
| 19 | Correct | 8 ms | 5964 KB | Output is correct |
| 20 | Correct | 7 ms | 5836 KB | Output is correct |
| 21 | Correct | 7 ms | 5780 KB | Output is correct |
| 22 | Correct | 8 ms | 5524 KB | Output is correct |
| 23 | Correct | 6 ms | 5196 KB | Output is correct |
| 24 | Correct | 9 ms | 6092 KB | Output is correct |
| 25 | Correct | 7 ms | 6036 KB | Output is correct |
| 26 | Correct | 9 ms | 6884 KB | Output is correct |
| 27 | Correct | 8 ms | 5908 KB | Output is correct |
| 28 | Correct | 11 ms | 6160 KB | Output is correct |
| 29 | Correct | 9 ms | 6552 KB | Output is correct |
| 30 | Correct | 9 ms | 6476 KB | Output is correct |
| 31 | Correct | 9 ms | 6464 KB | Output is correct |
| 32 | Correct | 10 ms | 5452 KB | Output is correct |
| 33 | Correct | 394 ms | 27020 KB | Output is correct |
| 34 | Correct | 276 ms | 12112 KB | Output is correct |
| 35 | Correct | 377 ms | 22980 KB | Output is correct |
| 36 | Correct | 296 ms | 12076 KB | Output is correct |
| 37 | Correct | 242 ms | 11772 KB | Output is correct |
| 38 | Correct | 171 ms | 11772 KB | Output is correct |
| 39 | Correct | 215 ms | 65076 KB | Output is correct |
| 40 | Correct | 205 ms | 64904 KB | Output is correct |
| 41 | Correct | 178 ms | 64764 KB | Output is correct |
| 42 | Correct | 204 ms | 40020 KB | Output is correct |
| 43 | Correct | 234 ms | 39876 KB | Output is correct |
| 44 | Correct | 452 ms | 27076 KB | Output is correct |
| 45 | Correct | 259 ms | 12012 KB | Output is correct |
| 46 | Correct | 121 ms | 11588 KB | Output is correct |
| 47 | Correct | 297 ms | 43672 KB | Output is correct |
| 48 | Correct | 171 ms | 36736 KB | Output is correct |
| 49 | Correct | 133 ms | 36636 KB | Output is correct |
| 50 | Correct | 284 ms | 21728 KB | Output is correct |
| 51 | Correct | 132 ms | 9336 KB | Output is correct |
| 52 | Correct | 304 ms | 44220 KB | Output is correct |
| 53 | Correct | 169 ms | 37188 KB | Output is correct |
| 54 | Correct | 286 ms | 77156 KB | Output is correct |
| 55 | Correct | 257 ms | 45832 KB | Output is correct |
| 56 | Correct | 238 ms | 60360 KB | Output is correct |
| 57 | Correct | 241 ms | 66804 KB | Output is correct |
| 58 | Correct | 283 ms | 64648 KB | Output is correct |
| 59 | Correct | 290 ms | 64764 KB | Output is correct |
| 60 | Correct | 3 ms | 4984 KB | Output is correct |
| 61 | Correct | 3 ms | 4996 KB | Output is correct |
| 62 | Correct | 3 ms | 4940 KB | Output is correct |
| 63 | Correct | 3 ms | 4984 KB | Output is correct |
| 64 | Correct | 378 ms | 26436 KB | Output is correct |
| 65 | Correct | 268 ms | 17704 KB | Output is correct |
| 66 | Correct | 416 ms | 29108 KB | Output is correct |
| 67 | Correct | 274 ms | 18284 KB | Output is correct |
| 68 | Correct | 195 ms | 17192 KB | Output is correct |
| 69 | Correct | 202 ms | 16996 KB | Output is correct |
| 70 | Correct | 336 ms | 37252 KB | Output is correct |
| 71 | Correct | 158 ms | 19876 KB | Output is correct |
| 72 | Correct | 439 ms | 44880 KB | Output is correct |
| 73 | Correct | 172 ms | 20156 KB | Output is correct |
| 74 | Correct | 421 ms | 35208 KB | Output is correct |
| 75 | Correct | 235 ms | 16588 KB | Output is correct |
| 76 | Correct | 165 ms | 16592 KB | Output is correct |
| 77 | Correct | 353 ms | 35516 KB | Output is correct |
| 78 | Correct | 156 ms | 17084 KB | Output is correct |
| 79 | Correct | 402 ms | 35348 KB | Output is correct |
| 80 | Correct | 220 ms | 18412 KB | Output is correct |
| 81 | Correct | 163 ms | 18208 KB | Output is correct |
| 82 | Correct | 272 ms | 45172 KB | Output is correct |
| 83 | Correct | 123 ms | 19068 KB | Output is correct |
| 84 | Correct | 307 ms | 48704 KB | Output is correct |
| 85 | Correct | 309 ms | 48704 KB | Output is correct |
| 86 | Correct | 282 ms | 42304 KB | Output is correct |
| 87 | Correct | 305 ms | 48704 KB | Output is correct |
| 88 | Correct | 306 ms | 48668 KB | Output is correct |