| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 390020 | 2021-04-15T05:34:21 Z | georgerapeanu | Worst Reporter 4 (JOI21_worst_reporter4) | C++11 | 487 ms | 125012 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 | 14 ms | 19112 KB | Output is correct |
| 2 | Correct | 14 ms | 19068 KB | Output is correct |
| 3 | Correct | 14 ms | 19160 KB | Output is correct |
| 4 | Correct | 13 ms | 19120 KB | Output is correct |
| 5 | Correct | 22 ms | 20792 KB | Output is correct |
| 6 | Correct | 19 ms | 20172 KB | Output is correct |
| 7 | Correct | 18 ms | 19920 KB | Output is correct |
| 8 | Correct | 21 ms | 20772 KB | Output is correct |
| 9 | Correct | 19 ms | 20172 KB | Output is correct |
| 10 | Correct | 18 ms | 20000 KB | Output is correct |
| 11 | Correct | 18 ms | 19788 KB | Output is correct |
| 12 | Correct | 21 ms | 20216 KB | Output is correct |
| 13 | Correct | 20 ms | 20136 KB | Output is correct |
| 14 | Correct | 18 ms | 19884 KB | Output is correct |
| 15 | Correct | 18 ms | 19916 KB | Output is correct |
| 16 | Correct | 22 ms | 21068 KB | Output is correct |
| 17 | Correct | 20 ms | 20420 KB | Output is correct |
| 18 | Correct | 17 ms | 19852 KB | Output is correct |
| 19 | Correct | 21 ms | 20428 KB | Output is correct |
| 20 | Correct | 18 ms | 20176 KB | Output is correct |
| 21 | Correct | 18 ms | 20136 KB | Output is correct |
| 22 | Correct | 19 ms | 20388 KB | Output is correct |
| 23 | Correct | 18 ms | 20044 KB | Output is correct |
| 24 | Correct | 20 ms | 20420 KB | Output is correct |
| 25 | Correct | 18 ms | 20172 KB | Output is correct |
| 26 | Incorrect | 20 ms | 20872 KB | Output isn't correct |
| 27 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 22 ms | 20816 KB | Output is correct |
| 2 | Correct | 466 ms | 98776 KB | Output is correct |
| 3 | Correct | 375 ms | 69288 KB | Output is correct |
| 4 | Correct | 487 ms | 96540 KB | Output is correct |
| 5 | Correct | 369 ms | 69256 KB | Output is correct |
| 6 | Correct | 271 ms | 50276 KB | Output is correct |
| 7 | Correct | 267 ms | 45928 KB | Output is correct |
| 8 | Correct | 225 ms | 61508 KB | Output is correct |
| 9 | Correct | 215 ms | 61648 KB | Output is correct |
| 10 | Correct | 153 ms | 61484 KB | Output is correct |
| 11 | Correct | 223 ms | 49092 KB | Output is correct |
| 12 | Correct | 222 ms | 49244 KB | Output is correct |
| 13 | Correct | 452 ms | 125012 KB | Output is correct |
| 14 | Correct | 337 ms | 83500 KB | Output is correct |
| 15 | Correct | 156 ms | 45756 KB | Output is correct |
| 16 | Correct | 414 ms | 72416 KB | Output is correct |
| 17 | Correct | 204 ms | 58452 KB | Output is correct |
| 18 | Correct | 159 ms | 58332 KB | Output is correct |
| 19 | Correct | 390 ms | 68724 KB | Output is correct |
| 20 | Correct | 177 ms | 55992 KB | Output is correct |
| 21 | Correct | 424 ms | 73060 KB | Output is correct |
| 22 | Correct | 196 ms | 58928 KB | Output is correct |
| 23 | Incorrect | 357 ms | 86428 KB | Output isn't correct |
| 24 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 14 ms | 19112 KB | Output is correct |
| 2 | Correct | 14 ms | 19068 KB | Output is correct |
| 3 | Correct | 14 ms | 19160 KB | Output is correct |
| 4 | Correct | 13 ms | 19120 KB | Output is correct |
| 5 | Correct | 22 ms | 20792 KB | Output is correct |
| 6 | Correct | 19 ms | 20172 KB | Output is correct |
| 7 | Correct | 18 ms | 19920 KB | Output is correct |
| 8 | Correct | 21 ms | 20772 KB | Output is correct |
| 9 | Correct | 19 ms | 20172 KB | Output is correct |
| 10 | Correct | 18 ms | 20000 KB | Output is correct |
| 11 | Correct | 18 ms | 19788 KB | Output is correct |
| 12 | Correct | 21 ms | 20216 KB | Output is correct |
| 13 | Correct | 20 ms | 20136 KB | Output is correct |
| 14 | Correct | 18 ms | 19884 KB | Output is correct |
| 15 | Correct | 18 ms | 19916 KB | Output is correct |
| 16 | Correct | 22 ms | 21068 KB | Output is correct |
| 17 | Correct | 20 ms | 20420 KB | Output is correct |
| 18 | Correct | 17 ms | 19852 KB | Output is correct |
| 19 | Correct | 21 ms | 20428 KB | Output is correct |
| 20 | Correct | 18 ms | 20176 KB | Output is correct |
| 21 | Correct | 18 ms | 20136 KB | Output is correct |
| 22 | Correct | 19 ms | 20388 KB | Output is correct |
| 23 | Correct | 18 ms | 20044 KB | Output is correct |
| 24 | Correct | 20 ms | 20420 KB | Output is correct |
| 25 | Correct | 18 ms | 20172 KB | Output is correct |
| 26 | Incorrect | 20 ms | 20872 KB | Output isn't correct |
| 27 | Halted | 0 ms | 0 KB | - |