| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 390028 | 2021-04-15T05:53:24 Z | georgerapeanu | Worst Reporter 4 (JOI21_worst_reporter4) | C++11 | 572 ms | 122820 KB |
#include <bits/stdc++.h>
using namespace std;
struct slope_magic_t{
map<int,long long> slope_change;
slope_magic_t(){
slope_change = map<int,long long>();
}
void merge(slope_magic_t &other){
for(auto it:other.slope_change){
slope_change[it.first] += it.second;
}
}
void add_value(int value,int cost){
slope_change[0] += cost;
slope_change[value] -= cost;
slope_change[value + 1] += cost;
long long relative_height = 0;
map<int,long long> :: iterator it,it2;
it = slope_change.lower_bound(value);
long long current_diff = slope_change[value];
while(current_diff < 0){
it2 = it;
if(it2 == slope_change.begin()){
break;
}
it2--;
if(it2 == slope_change.begin() || current_diff + it2->second >= 0){
it2->second += current_diff;
slope_change.erase(it);
break;
}
relative_height = -current_diff - it2->second;
slope_change.erase(it2);
current_diff = -relative_height;
}
}
int size(){
return (int)slope_change.size();
}
void swap(slope_magic_t &other){
slope_change.swap(other.slope_change);
}
};
const int NMAX = 2e5;
int n;
slope_magic_t dp[NMAX + 5];
vector<int> graph[NMAX + 5];
vector<int> graph2[NMAX + 5];
int father[NMAX + 5];
int c[NMAX + 5];
int h[NMAX + 5];
bool viz[NMAX + 5];
void dfs(int nod){
viz[nod] = true;
for(auto it:graph[nod]){
dfs(it);
if(dp[it].size() > dp[nod].size()){
dp[nod].swap(dp[it]);
}
dp[nod].merge(dp[it]);
}
dp[nod].add_value(h[nod],c[nod]);
}
int lvl[NMAX + 5];
int st[NMAX + 5];
int len;
vector<int> cycle;
bool on_cycle[NMAX + 5];
void predfs(int nod){
st[++len] = nod;
lvl[nod] = len;
viz[nod] = true;
for(auto it:graph2[nod]){
if(viz[it] == false){
predfs(it);
}else{
for(int i = lvl[it];i <= lvl[nod];i++){
on_cycle[st[i]] = true;
cycle.push_back(st[i]);
}
}
}
len--;
}
long long solve(int nod){
cycle.clear();
predfs(nod);
slope_magic_t global;
for(auto it:cycle){
for(auto it2:graph[it]){
if(on_cycle[it2] == false){
dfs(it2);
global.merge(dp[it2]);
}
}
}
for(auto it:cycle){
global.slope_change[0] += c[it];
global.slope_change[h[it]] -= c[it];
global.slope_change[h[it] + 1] += c[it];
}
long long curr_cost = 0;
long long ans = 2e18;
for(auto it:global.slope_change){
curr_cost += it.second;
ans = min(ans,curr_cost);
}
return ans;
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%d %d %d",&father[i],&h[i],&c[i]);
graph[father[i]].push_back(i);
graph2[i].push_back(father[i]);
}
long long ans = 0;
for(int i = 1;i <= n;i++){
if(viz[i] == false){
long long tmp = solve(i);
ans += tmp;
}
}
printf("%lld\n",ans);
return 0;
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 13 ms | 19004 KB | Output is correct |
| 2 | Correct | 14 ms | 19120 KB | Output is correct |
| 3 | Correct | 14 ms | 19020 KB | Output is correct |
| 4 | Correct | 14 ms | 19020 KB | Output is correct |
| 5 | Correct | 21 ms | 20624 KB | Output is correct |
| 6 | Correct | 20 ms | 20052 KB | Output is correct |
| 7 | Correct | 18 ms | 19824 KB | Output is correct |
| 8 | Correct | 21 ms | 20684 KB | Output is correct |
| 9 | Correct | 19 ms | 20068 KB | Output is correct |
| 10 | Correct | 22 ms | 19860 KB | Output is correct |
| 11 | Correct | 18 ms | 19740 KB | Output is correct |
| 12 | Correct | 19 ms | 20144 KB | Output is correct |
| 13 | Correct | 19 ms | 20172 KB | Output is correct |
| 14 | Correct | 20 ms | 19820 KB | Output is correct |
| 15 | Correct | 17 ms | 19824 KB | Output is correct |
| 16 | Correct | 22 ms | 21044 KB | Output is correct |
| 17 | Correct | 19 ms | 20304 KB | Output is correct |
| 18 | Correct | 18 ms | 19680 KB | Output is correct |
| 19 | Correct | 19 ms | 20328 KB | Output is correct |
| 20 | Correct | 17 ms | 20044 KB | Output is correct |
| 21 | Correct | 17 ms | 20032 KB | Output is correct |
| 22 | Correct | 19 ms | 20300 KB | Output is correct |
| 23 | Correct | 17 ms | 19916 KB | Output is correct |
| 24 | Correct | 21 ms | 20380 KB | Output is correct |
| 25 | Correct | 17 ms | 20048 KB | Output is correct |
| 26 | Correct | 20 ms | 20752 KB | Output is correct |
| 27 | Correct | 21 ms | 20540 KB | Output is correct |
| 28 | Correct | 22 ms | 20556 KB | Output is correct |
| 29 | Correct | 20 ms | 20684 KB | Output is correct |
| 30 | Correct | 19 ms | 20428 KB | Output is correct |
| 31 | Correct | 19 ms | 20428 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 22 ms | 20772 KB | Output is correct |
| 2 | Correct | 473 ms | 96220 KB | Output is correct |
| 3 | Correct | 357 ms | 66884 KB | Output is correct |
| 4 | Correct | 462 ms | 94320 KB | Output is correct |
| 5 | Correct | 351 ms | 67012 KB | Output is correct |
| 6 | Correct | 278 ms | 47888 KB | Output is correct |
| 7 | Correct | 262 ms | 43552 KB | Output is correct |
| 8 | Correct | 225 ms | 59316 KB | Output is correct |
| 9 | Correct | 227 ms | 59264 KB | Output is correct |
| 10 | Correct | 155 ms | 59276 KB | Output is correct |
| 11 | Correct | 222 ms | 46812 KB | Output is correct |
| 12 | Correct | 207 ms | 46712 KB | Output is correct |
| 13 | Correct | 459 ms | 122820 KB | Output is correct |
| 14 | Correct | 313 ms | 81128 KB | Output is correct |
| 15 | Correct | 158 ms | 43584 KB | Output is correct |
| 16 | Correct | 410 ms | 69936 KB | Output is correct |
| 17 | Correct | 199 ms | 56176 KB | Output is correct |
| 18 | Correct | 160 ms | 56044 KB | Output is correct |
| 19 | Correct | 432 ms | 66260 KB | Output is correct |
| 20 | Correct | 173 ms | 53692 KB | Output is correct |
| 21 | Correct | 464 ms | 70824 KB | Output is correct |
| 22 | Correct | 189 ms | 56484 KB | Output is correct |
| 23 | Correct | 356 ms | 84340 KB | Output is correct |
| 24 | Correct | 380 ms | 75716 KB | Output is correct |
| 25 | Correct | 321 ms | 78764 KB | Output is correct |
| 26 | Correct | 305 ms | 80840 KB | Output is correct |
| 27 | Correct | 317 ms | 73036 KB | Output is correct |
| 28 | Correct | 312 ms | 72992 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 13 ms | 19004 KB | Output is correct |
| 2 | Correct | 14 ms | 19120 KB | Output is correct |
| 3 | Correct | 14 ms | 19020 KB | Output is correct |
| 4 | Correct | 14 ms | 19020 KB | Output is correct |
| 5 | Correct | 21 ms | 20624 KB | Output is correct |
| 6 | Correct | 20 ms | 20052 KB | Output is correct |
| 7 | Correct | 18 ms | 19824 KB | Output is correct |
| 8 | Correct | 21 ms | 20684 KB | Output is correct |
| 9 | Correct | 19 ms | 20068 KB | Output is correct |
| 10 | Correct | 22 ms | 19860 KB | Output is correct |
| 11 | Correct | 18 ms | 19740 KB | Output is correct |
| 12 | Correct | 19 ms | 20144 KB | Output is correct |
| 13 | Correct | 19 ms | 20172 KB | Output is correct |
| 14 | Correct | 20 ms | 19820 KB | Output is correct |
| 15 | Correct | 17 ms | 19824 KB | Output is correct |
| 16 | Correct | 22 ms | 21044 KB | Output is correct |
| 17 | Correct | 19 ms | 20304 KB | Output is correct |
| 18 | Correct | 18 ms | 19680 KB | Output is correct |
| 19 | Correct | 19 ms | 20328 KB | Output is correct |
| 20 | Correct | 17 ms | 20044 KB | Output is correct |
| 21 | Correct | 17 ms | 20032 KB | Output is correct |
| 22 | Correct | 19 ms | 20300 KB | Output is correct |
| 23 | Correct | 17 ms | 19916 KB | Output is correct |
| 24 | Correct | 21 ms | 20380 KB | Output is correct |
| 25 | Correct | 17 ms | 20048 KB | Output is correct |
| 26 | Correct | 20 ms | 20752 KB | Output is correct |
| 27 | Correct | 21 ms | 20540 KB | Output is correct |
| 28 | Correct | 22 ms | 20556 KB | Output is correct |
| 29 | Correct | 20 ms | 20684 KB | Output is correct |
| 30 | Correct | 19 ms | 20428 KB | Output is correct |
| 31 | Correct | 19 ms | 20428 KB | Output is correct |
| 32 | Correct | 22 ms | 20772 KB | Output is correct |
| 33 | Correct | 473 ms | 96220 KB | Output is correct |
| 34 | Correct | 357 ms | 66884 KB | Output is correct |
| 35 | Correct | 462 ms | 94320 KB | Output is correct |
| 36 | Correct | 351 ms | 67012 KB | Output is correct |
| 37 | Correct | 278 ms | 47888 KB | Output is correct |
| 38 | Correct | 262 ms | 43552 KB | Output is correct |
| 39 | Correct | 225 ms | 59316 KB | Output is correct |
| 40 | Correct | 227 ms | 59264 KB | Output is correct |
| 41 | Correct | 155 ms | 59276 KB | Output is correct |
| 42 | Correct | 222 ms | 46812 KB | Output is correct |
| 43 | Correct | 207 ms | 46712 KB | Output is correct |
| 44 | Correct | 459 ms | 122820 KB | Output is correct |
| 45 | Correct | 313 ms | 81128 KB | Output is correct |
| 46 | Correct | 158 ms | 43584 KB | Output is correct |
| 47 | Correct | 410 ms | 69936 KB | Output is correct |
| 48 | Correct | 199 ms | 56176 KB | Output is correct |
| 49 | Correct | 160 ms | 56044 KB | Output is correct |
| 50 | Correct | 432 ms | 66260 KB | Output is correct |
| 51 | Correct | 173 ms | 53692 KB | Output is correct |
| 52 | Correct | 464 ms | 70824 KB | Output is correct |
| 53 | Correct | 189 ms | 56484 KB | Output is correct |
| 54 | Correct | 356 ms | 84340 KB | Output is correct |
| 55 | Correct | 380 ms | 75716 KB | Output is correct |
| 56 | Correct | 321 ms | 78764 KB | Output is correct |
| 57 | Correct | 305 ms | 80840 KB | Output is correct |
| 58 | Correct | 317 ms | 73036 KB | Output is correct |
| 59 | Correct | 312 ms | 72992 KB | Output is correct |
| 60 | Correct | 13 ms | 19020 KB | Output is correct |
| 61 | Correct | 14 ms | 19096 KB | Output is correct |
| 62 | Correct | 14 ms | 19096 KB | Output is correct |
| 63 | Correct | 13 ms | 19024 KB | Output is correct |
| 64 | Correct | 472 ms | 88000 KB | Output is correct |
| 65 | Correct | 369 ms | 64352 KB | Output is correct |
| 66 | Correct | 443 ms | 78868 KB | Output is correct |
| 67 | Correct | 392 ms | 64260 KB | Output is correct |
| 68 | Correct | 272 ms | 50632 KB | Output is correct |
| 69 | Correct | 253 ms | 47272 KB | Output is correct |
| 70 | Correct | 449 ms | 69728 KB | Output is correct |
| 71 | Correct | 248 ms | 49220 KB | Output is correct |
| 72 | Correct | 538 ms | 82452 KB | Output is correct |
| 73 | Correct | 252 ms | 57796 KB | Output is correct |
| 74 | Correct | 572 ms | 76916 KB | Output is correct |
| 75 | Correct | 305 ms | 58328 KB | Output is correct |
| 76 | Correct | 303 ms | 58228 KB | Output is correct |
| 77 | Correct | 463 ms | 77424 KB | Output is correct |
| 78 | Correct | 227 ms | 58680 KB | Output is correct |
| 79 | Correct | 485 ms | 92552 KB | Output is correct |
| 80 | Correct | 323 ms | 66624 KB | Output is correct |
| 81 | Correct | 261 ms | 56020 KB | Output is correct |
| 82 | Correct | 353 ms | 82708 KB | Output is correct |
| 83 | Correct | 149 ms | 40136 KB | Output is correct |
| 84 | Correct | 409 ms | 78120 KB | Output is correct |
| 85 | Correct | 404 ms | 78020 KB | Output is correct |
| 86 | Correct | 421 ms | 71748 KB | Output is correct |
| 87 | Correct | 419 ms | 79052 KB | Output is correct |
| 88 | Correct | 422 ms | 80832 KB | Output is correct |