oj.uz

Submission #390020

# Submission time Handle Problem Language Result Execution time Memory
390020 2021-04-15T05:34:21 Z georgerapeanu Worst Reporter 4 (JOI21_worst_reporter4) C++11
0 / 100
 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

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
worst_reporter2.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  140 |         scanf("%d %d %d",&father[i],&h[i],&c[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory 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 -

Subtask #2
0 / 65.0

# Verdict Execution time Memory 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 -

Subtask #3
0 / 21.0

# Verdict Execution time Memory 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 -