oj.uz

답안 #389884

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
389884 2021-04-14T19:10:59 Z georgerapeanu Worst Reporter 4 (JOI21_worst_reporter4) C++11
0 / 100
 468 ms 126644 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,int lvl){
    viz[nod] = true;
    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]);
}

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,0);
                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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19096 KB Output is correct
2 Correct 12 ms 19104 KB Output is correct
3 Correct 12 ms 19128 KB Output is correct
4 Correct 12 ms 19104 KB Output is correct
5 Correct 20 ms 20796 KB Output is correct
6 Correct 17 ms 20124 KB Output is correct
7 Correct 17 ms 20008 KB Output is correct
8 Correct 20 ms 20812 KB Output is correct
9 Correct 18 ms 20172 KB Output is correct
10 Correct 17 ms 19992 KB Output is correct
11 Correct 16 ms 19860 KB Output is correct
12 Correct 18 ms 20264 KB Output is correct
13 Correct 16 ms 20256 KB Output is correct
14 Correct 17 ms 19936 KB Output is correct
15 Correct 16 ms 19984 KB Output is correct
16 Correct 20 ms 21156 KB Output is correct
17 Correct 18 ms 20348 KB Output is correct
18 Correct 16 ms 19788 KB Output is correct
19 Correct 20 ms 20492 KB Output is correct
20 Correct 17 ms 20104 KB Output is correct
21 Correct 16 ms 20172 KB Output is correct
22 Correct 18 ms 20356 KB Output is correct
23 Correct 16 ms 20044 KB Output is correct
24 Correct 18 ms 20536 KB Output is correct
25 Correct 17 ms 20300 KB Output is correct
26 Incorrect 19 ms 20948 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 20792 KB Output is correct
2 Correct 468 ms 99924 KB Output is correct
3 Correct 355 ms 70724 KB Output is correct
4 Correct 447 ms 98076 KB Output is correct
5 Correct 343 ms 70852 KB Output is correct
6 Correct 258 ms 51888 KB Output is correct
7 Correct 244 ms 47412 KB Output is correct
8 Correct 223 ms 66208 KB Output is correct
9 Correct 211 ms 66116 KB Output is correct
10 Correct 148 ms 66288 KB Output is correct
11 Correct 214 ms 52164 KB Output is correct
12 Correct 203 ms 52020 KB Output is correct
13 Correct 465 ms 126644 KB Output is correct
14 Correct 314 ms 84892 KB Output is correct
15 Correct 163 ms 47412 KB Output is correct
16 Correct 397 ms 75332 KB Output is correct
17 Correct 205 ms 61508 KB Output is correct
18 Correct 155 ms 61304 KB Output is correct
19 Correct 374 ms 70052 KB Output is correct
20 Correct 173 ms 57488 KB Output is correct
21 Correct 409 ms 76108 KB Output is correct
22 Correct 186 ms 61856 KB Output is correct
23 Incorrect 354 ms 91044 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19096 KB Output is correct
2 Correct 12 ms 19104 KB Output is correct
3 Correct 12 ms 19128 KB Output is correct
4 Correct 12 ms 19104 KB Output is correct
5 Correct 20 ms 20796 KB Output is correct
6 Correct 17 ms 20124 KB Output is correct
7 Correct 17 ms 20008 KB Output is correct
8 Correct 20 ms 20812 KB Output is correct
9 Correct 18 ms 20172 KB Output is correct
10 Correct 17 ms 19992 KB Output is correct
11 Correct 16 ms 19860 KB Output is correct
12 Correct 18 ms 20264 KB Output is correct
13 Correct 16 ms 20256 KB Output is correct
14 Correct 17 ms 19936 KB Output is correct
15 Correct 16 ms 19984 KB Output is correct
16 Correct 20 ms 21156 KB Output is correct
17 Correct 18 ms 20348 KB Output is correct
18 Correct 16 ms 19788 KB Output is correct
19 Correct 20 ms 20492 KB Output is correct
20 Correct 17 ms 20104 KB Output is correct
21 Correct 16 ms 20172 KB Output is correct
22 Correct 18 ms 20356 KB Output is correct
23 Correct 16 ms 20044 KB Output is correct
24 Correct 18 ms 20536 KB Output is correct
25 Correct 17 ms 20300 KB Output is correct
26 Incorrect 19 ms 20948 KB Output isn't correct
27 Halted 0 ms 0 KB -