oj.uz

답안 #914750

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
914750 2024-01-22T16:01:18 Z minhnhatnoe Worst Reporter 4 (JOI21_worst_reporter4) C++17
0 / 100
 7 ms 15368 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 200000;

int a[MAXN], h[MAXN], c[MAXN], deg[MAXN], n;
map<int, long long> s[MAXN];
vector<int> q;

// dp(v, i) =
// h[v] < i: \sum{dp(u, i)}
// h[v] >= i: max(\sum{dp(u, i)}, c[v] + \sum{dp(u, h[v])})
void cdeg(int v){
    if (deg[v]) return;
    auto it = s[v].lower_bound(h[v]);
    if (it == s[v].end() || it->first != h[v])
        it = s[v].emplace_hint(it, h[v], 0);
    it->second += c[v];

    for (int x = c[v]; it != s[v].begin() && x;){
        it--;
        if (it->second <= x){
            x -= it->second;
            it = s[v].erase(it);
        }
        else{
            it->second -= x;
            x = 0;
        }
    }
    q.push_back(v);
}

void merge(map<int, long long> &a, map<int, long long> &b){
    if (a.size() < b.size()) swap(a, b);
    a.merge(b);
}

long long pfm(map<int, long long> &hs){
    long long p = 0;
    for (auto it = hs.rbegin(); it != hs.rend(); it++)
        p = it->second = p + it->second;
    hs.emplace_hint(hs.end(), INT_MAX, 0);
    return p;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i=0; i<n; i++){
        cin >> a[i] >> h[i] >> c[i];
        a[i]--, deg[a[i]]++;
    }

    for (int i=0; i<n; i++)
        cdeg(i);

    long long result = accumulate(c, c + n, 0LL);
    while (q.size()){
        int v = q.back(); q.pop_back();
        merge(s[a[v]], s[v]);
        deg[a[v]]--, cdeg(a[v]);
    }

    for (int i=0; i<n; i++){
        if (!deg[i]) continue;
        vector<pair<int, int>> cyc;
        map<int, long long> hs;
        for (int pos = i; deg[pos]; deg[pos] = 0, pos = a[pos]){
            merge(hs, s[pos]);
            cyc.emplace_back(h[pos], c[pos]);
        }
        sort(cyc.begin(), cyc.end());

        long long max_branch = pfm(hs);
        for (int lptr=0, rptr=0; lptr<cyc.size(); lptr=rptr){
            long long v = hs.lower_bound(cyc[lptr].first)->second;
            for (; rptr < cyc.size() && cyc[lptr].first == cyc[rptr].first; rptr++)
                v += cyc[rptr].second;
            max_branch = max(max_branch, v);
        }
        result -= max_branch;
    }
    cout << result << "\n";
}

Compilation message

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:76:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int lptr=0, rptr=0; lptr<cyc.size(); lptr=rptr){
      |                                  ~~~~^~~~~~~~~~~
worst_reporter2.cpp:78:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for (; rptr < cyc.size() && cyc[lptr].first == cyc[rptr].first; rptr++)
      |                    ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 4 ms 14952 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 7 ms 15368 KB Output is correct
6 Incorrect 6 ms 15196 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 4 ms 14952 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 7 ms 15368 KB Output is correct
6 Incorrect 6 ms 15196 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 4 ms 14952 KB Output is correct
3 Correct 5 ms 14940 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 7 ms 15368 KB Output is correct
6 Incorrect 6 ms 15196 KB Output isn't correct
7 Halted 0 ms 0 KB -