| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 389801 | 2021-04-14T14:30:17 Z | georgerapeanu | Worst Reporter 4 (JOI21_worst_reporter4) | C++11 | 2000 ms | 113772 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];
int father[NMAX + 5];
int c[NMAX + 5];
int h[NMAX + 5];
void dfs(int nod,int lvl){
for(auto it:graph[nod]){
dfs(it,lvl + 1);
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]);
}
bool viz[NMAX + 5];
int lvl[NMAX + 5];
int st[NMAX + 5];
int len;
vector<int> curr_nodes;
bool on_cycle[NMAX + 5];
void predfs(int nod,int tata){
curr_nodes.push_back(nod);
st[++len] = nod;
lvl[nod] = len;
viz[nod] = true;
for(auto it:graph[nod]){
if(it == tata){
continue;
}
for(auto it:graph[nod]){
if(viz[it] == false){
predfs(it,nod);
}else{
for(int i = lvl[it];i <= lvl[nod];i++){
on_cycle[st[i]] = true;
}
}
}
}
len--;
}
long long solve(int nod){
curr_nodes.clear();
predfs(nod,0);
slope_magic_t global;
for(auto it:curr_nodes){
if(on_cycle[it]){
for(auto it2:graph[it]){
if(on_cycle[it2] == false){
dfs(it2,0);
global.merge(dp[it2]);
}
}
}
}
for(auto it:curr_nodes){
if(on_cycle[it]){
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);
}
long long ans = 0;
for(int i = 1;i <= n;i++){
if(viz[i] == false){
ans += solve(i);
}
}
printf("%lld\n",ans);
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 14424 KB | Output is correct |
| 2 | Correct | 10 ms | 14344 KB | Output is correct |
| 3 | Correct | 10 ms | 14412 KB | Output is correct |
| 4 | Correct | 10 ms | 14412 KB | Output is correct |
| 5 | Correct | 18 ms | 15948 KB | Output is correct |
| 6 | Correct | 16 ms | 15184 KB | Output is correct |
| 7 | Correct | 15 ms | 15080 KB | Output is correct |
| 8 | Correct | 18 ms | 15820 KB | Output is correct |
| 9 | Correct | 16 ms | 15280 KB | Output is correct |
| 10 | Correct | 15 ms | 15052 KB | Output is correct |
| 11 | Correct | 17 ms | 14928 KB | Output is correct |
| 12 | Correct | 18 ms | 15420 KB | Output is correct |
| 13 | Correct | 14 ms | 15324 KB | Output is correct |
| 14 | Correct | 16 ms | 14992 KB | Output is correct |
| 15 | Correct | 15 ms | 15052 KB | Output is correct |
| 16 | Correct | 19 ms | 16204 KB | Output is correct |
| 17 | Correct | 18 ms | 15416 KB | Output is correct |
| 18 | Correct | 15 ms | 14796 KB | Output is correct |
| 19 | Correct | 16 ms | 15608 KB | Output is correct |
| 20 | Correct | 15 ms | 15180 KB | Output is correct |
| 21 | Correct | 14 ms | 15180 KB | Output is correct |
| 22 | Correct | 43 ms | 15468 KB | Output is correct |
| 23 | Correct | 45 ms | 15180 KB | Output is correct |
| 24 | Correct | 23 ms | 15608 KB | Output is correct |
| 25 | Correct | 21 ms | 15224 KB | Output is correct |
| 26 | Incorrect | 16 ms | 15948 KB | Output isn't correct |
| 27 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 18 ms | 15968 KB | Output is correct |
| 2 | Correct | 471 ms | 87092 KB | Output is correct |
| 3 | Correct | 350 ms | 57864 KB | Output is correct |
| 4 | Correct | 481 ms | 85256 KB | Output is correct |
| 5 | Correct | 387 ms | 57916 KB | Output is correct |
| 6 | Correct | 268 ms | 38964 KB | Output is correct |
| 7 | Correct | 239 ms | 34620 KB | Output is correct |
| 8 | Correct | 225 ms | 54204 KB | Output is correct |
| 9 | Correct | 209 ms | 54200 KB | Output is correct |
| 10 | Correct | 153 ms | 54108 KB | Output is correct |
| 11 | Correct | 214 ms | 39824 KB | Output is correct |
| 12 | Correct | 199 ms | 39644 KB | Output is correct |
| 13 | Correct | 436 ms | 113772 KB | Output is correct |
| 14 | Correct | 306 ms | 72128 KB | Output is correct |
| 15 | Correct | 176 ms | 34468 KB | Output is correct |
| 16 | Correct | 390 ms | 62832 KB | Output is correct |
| 17 | Correct | 189 ms | 49096 KB | Output is correct |
| 18 | Correct | 166 ms | 48980 KB | Output is correct |
| 19 | Execution timed out | 2068 ms | 20024 KB | Time limit exceeded |
| 20 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 14424 KB | Output is correct |
| 2 | Correct | 10 ms | 14344 KB | Output is correct |
| 3 | Correct | 10 ms | 14412 KB | Output is correct |
| 4 | Correct | 10 ms | 14412 KB | Output is correct |
| 5 | Correct | 18 ms | 15948 KB | Output is correct |
| 6 | Correct | 16 ms | 15184 KB | Output is correct |
| 7 | Correct | 15 ms | 15080 KB | Output is correct |
| 8 | Correct | 18 ms | 15820 KB | Output is correct |
| 9 | Correct | 16 ms | 15280 KB | Output is correct |
| 10 | Correct | 15 ms | 15052 KB | Output is correct |
| 11 | Correct | 17 ms | 14928 KB | Output is correct |
| 12 | Correct | 18 ms | 15420 KB | Output is correct |
| 13 | Correct | 14 ms | 15324 KB | Output is correct |
| 14 | Correct | 16 ms | 14992 KB | Output is correct |
| 15 | Correct | 15 ms | 15052 KB | Output is correct |
| 16 | Correct | 19 ms | 16204 KB | Output is correct |
| 17 | Correct | 18 ms | 15416 KB | Output is correct |
| 18 | Correct | 15 ms | 14796 KB | Output is correct |
| 19 | Correct | 16 ms | 15608 KB | Output is correct |
| 20 | Correct | 15 ms | 15180 KB | Output is correct |
| 21 | Correct | 14 ms | 15180 KB | Output is correct |
| 22 | Correct | 43 ms | 15468 KB | Output is correct |
| 23 | Correct | 45 ms | 15180 KB | Output is correct |
| 24 | Correct | 23 ms | 15608 KB | Output is correct |
| 25 | Correct | 21 ms | 15224 KB | Output is correct |
| 26 | Incorrect | 16 ms | 15948 KB | Output isn't correct |
| 27 | Halted | 0 ms | 0 KB | - |