oj.uz

Submission #435837

# Submission time Handle Problem Language Result Execution time Memory
435837 2021-06-23T19:17:33 Z 2qbingxuan Worst Reporter 4 (JOI21_worst_reporter4) C++14
79 / 100
 426 ms 103288 KB 
#include <bits/stdc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) qqbx(#a, a)
#define pary(a...) danb(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
    int cnt = sizeof...(T);
    ((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : ")\033[0m\n")));
}
template <typename T> void danb(const char *s, T L, T R) {
    std::cerr << "\033[1;32m[ " << s << " ] = [ ";
    for (auto it = L; it != R; ++it)
        std::cerr << *it << ' ';
    std::cerr << "]\033[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define pary(...) ((void)0)
#endif // local
#define all(v) begin(v),end(v)
 
using namespace std;
using ll = int64_t;
const int maxn = 200025, maxm = 10000;
 
int H[maxn], C[maxn];
vector<int> g[maxn];
map<int,ll,greater<>> sub[maxn];
int cyc[maxn];
void join(int a, int b) {
    if (sub[a].size() > sub[b].size())
        swap(sub[a], sub[b]);
    for (auto [h, val]: sub[a])
        sub[b][h] += val;
}
void dfs(int i) {
    for (int j: g[i]) {
        dfs(j);
        join(j, i);
    }
    sub[i][H[i]] += C[i];
    auto it = sub[i].upper_bound(H[i]);
    ll v = C[i];
    while (it != sub[i].end()) {
        if (it->second < v) {
            v -= it->second;
            sub[i].erase(it++);
        } else {
            it->second -= v;
            break;
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    ll tot = 0;
    vector<int> A(n);
    vector<int> indeg(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i] >> H[i] >> C[i];
        tot += C[i];
        --A[i];
        ++indeg[A[i]];
        g[A[i]].push_back(i);
    }
    for (int i = 0; i < n; i++) cyc[i] = -1;
    queue<int> que;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) que.push(i), cyc[i] = 0;
    while (!que.empty()) {
        int i = que.front(); que.pop();
        int j = A[i];
        if (--indeg[j] == 0)
            que.push(j), cyc[j] = 0;
    }
    vector<vector<int>> roots;
    roots.reserve(n);
    for (int i = 0, tot = 0; i < n; i++) if (cyc[i] == -1) {
        roots.emplace_back();
        roots.back().emplace_back(i);
        cyc[i] = ++tot;
        for (int x = A[i]; x != i; x = A[x]) {
            roots.back().emplace_back(x);
            cyc[x] = cyc[i];
        }
    }
    ll ans = 0;
    for (auto R: roots) {
        map<int,ll> best;
        for (int x: R) {
            ll dp = C[x];
            for (int y: g[x]) {
                if (cyc[y]) continue;
                dfs(y);
                for (auto [h, val]: sub[y]) if (h >= H[x]) dp += val;
                join(y, R[0]);
            }
            best[H[x]] += dp;
        }
        ll mx = 0;
        for (auto [h, val]: sub[R[0]]) mx += val;
        for (auto [h, val]: best) mx = max(mx, val);
        ans += mx;
    }
    cout << tot - ans << '\n';
}

Compilation message

worst_reporter2.cpp: In function 'void join(int, int)':
worst_reporter2.cpp:34:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     for (auto [h, val]: sub[a])
      |               ^
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:97:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   97 |                 for (auto [h, val]: sub[y]) if (h >= H[x]) dp += val;
      |                           ^
worst_reporter2.cpp:103:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  103 |         for (auto [h, val]: sub[R[0]]) mx += val;
      |                   ^
worst_reporter2.cpp:104:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  104 |         for (auto [h, val]: best) mx = max(mx, val);
      |                   ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14364 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 10 ms 14296 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 17 ms 15564 KB Output is correct
6 Correct 14 ms 15028 KB Output is correct
7 Correct 13 ms 14808 KB Output is correct
8 Correct 15 ms 15588 KB Output is correct
9 Correct 13 ms 15048 KB Output is correct
10 Correct 12 ms 14924 KB Output is correct
11 Correct 12 ms 14744 KB Output is correct
12 Correct 12 ms 15052 KB Output is correct
13 Correct 11 ms 15052 KB Output is correct
14 Correct 12 ms 14968 KB Output is correct
15 Correct 12 ms 14796 KB Output is correct
16 Correct 15 ms 15948 KB Output is correct
17 Correct 14 ms 15288 KB Output is correct
18 Correct 14 ms 14668 KB Output is correct
19 Correct 13 ms 15052 KB Output is correct
20 Correct 12 ms 14952 KB Output is correct
21 Correct 13 ms 14924 KB Output is correct
22 Correct 15 ms 15180 KB Output is correct
23 Correct 14 ms 14872 KB Output is correct
24 Correct 13 ms 15148 KB Output is correct
25 Correct 11 ms 14900 KB Output is correct
26 Correct 13 ms 15316 KB Output is correct
27 Correct 13 ms 15068 KB Output is correct
28 Correct 12 ms 15180 KB Output is correct
29 Correct 13 ms 15252 KB Output is correct
30 Correct 13 ms 15308 KB Output is correct
31 Correct 14 ms 15308 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14364 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 10 ms 14296 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 17 ms 15564 KB Output is correct
6 Correct 14 ms 15028 KB Output is correct
7 Correct 13 ms 14808 KB Output is correct
8 Correct 15 ms 15588 KB Output is correct
9 Correct 13 ms 15048 KB Output is correct
10 Correct 12 ms 14924 KB Output is correct
11 Correct 12 ms 14744 KB Output is correct
12 Correct 12 ms 15052 KB Output is correct
13 Correct 11 ms 15052 KB Output is correct
14 Correct 12 ms 14968 KB Output is correct
15 Correct 12 ms 14796 KB Output is correct
16 Correct 15 ms 15948 KB Output is correct
17 Correct 14 ms 15288 KB Output is correct
18 Correct 14 ms 14668 KB Output is correct
19 Correct 13 ms 15052 KB Output is correct
20 Correct 12 ms 14952 KB Output is correct
21 Correct 13 ms 14924 KB Output is correct
22 Correct 15 ms 15180 KB Output is correct
23 Correct 14 ms 14872 KB Output is correct
24 Correct 13 ms 15148 KB Output is correct
25 Correct 11 ms 14900 KB Output is correct
26 Correct 13 ms 15316 KB Output is correct
27 Correct 13 ms 15068 KB Output is correct
28 Correct 12 ms 15180 KB Output is correct
29 Correct 13 ms 15252 KB Output is correct
30 Correct 13 ms 15308 KB Output is correct
31 Correct 14 ms 15308 KB Output is correct
32 Correct 17 ms 15588 KB Output is correct
33 Correct 423 ms 75960 KB Output is correct
34 Correct 319 ms 53416 KB Output is correct
35 Correct 426 ms 75232 KB Output is correct
36 Correct 311 ms 53444 KB Output is correct
37 Correct 225 ms 34500 KB Output is correct
38 Correct 199 ms 29936 KB Output is correct
39 Correct 176 ms 42760 KB Output is correct
40 Correct 156 ms 42740 KB Output is correct
41 Correct 131 ms 42640 KB Output is correct
42 Correct 162 ms 34900 KB Output is correct
43 Correct 155 ms 35000 KB Output is correct
44 Correct 418 ms 103288 KB Output is correct
45 Correct 262 ms 67652 KB Output is correct
46 Correct 115 ms 30020 KB Output is correct
47 Correct 269 ms 44808 KB Output is correct
48 Correct 139 ms 37844 KB Output is correct
49 Correct 120 ms 37828 KB Output is correct
50 Correct 307 ms 45800 KB Output is correct
51 Correct 122 ms 33220 KB Output is correct
52 Correct 317 ms 45432 KB Output is correct
53 Correct 133 ms 38440 KB Output is correct
54 Correct 248 ms 55404 KB Output is correct
55 Correct 245 ms 46404 KB Output is correct
56 Correct 203 ms 49264 KB Output is correct
57 Correct 191 ms 50884 KB Output is correct
58 Correct 210 ms 52880 KB Output is correct
59 Correct 247 ms 52908 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14364 KB Output is correct
2 Correct 8 ms 14412 KB Output is correct
3 Correct 10 ms 14296 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 17 ms 15564 KB Output is correct
6 Correct 14 ms 15028 KB Output is correct
7 Correct 13 ms 14808 KB Output is correct
8 Correct 15 ms 15588 KB Output is correct
9 Correct 13 ms 15048 KB Output is correct
10 Correct 12 ms 14924 KB Output is correct
11 Correct 12 ms 14744 KB Output is correct
12 Correct 12 ms 15052 KB Output is correct
13 Correct 11 ms 15052 KB Output is correct
14 Correct 12 ms 14968 KB Output is correct
15 Correct 12 ms 14796 KB Output is correct
16 Correct 15 ms 15948 KB Output is correct
17 Correct 14 ms 15288 KB Output is correct
18 Correct 14 ms 14668 KB Output is correct
19 Correct 13 ms 15052 KB Output is correct
20 Correct 12 ms 14952 KB Output is correct
21 Correct 13 ms 14924 KB Output is correct
22 Correct 15 ms 15180 KB Output is correct
23 Correct 14 ms 14872 KB Output is correct
24 Correct 13 ms 15148 KB Output is correct
25 Correct 11 ms 14900 KB Output is correct
26 Correct 13 ms 15316 KB Output is correct
27 Correct 13 ms 15068 KB Output is correct
28 Correct 12 ms 15180 KB Output is correct
29 Correct 13 ms 15252 KB Output is correct
30 Correct 13 ms 15308 KB Output is correct
31 Correct 14 ms 15308 KB Output is correct
32 Correct 17 ms 15588 KB Output is correct
33 Correct 423 ms 75960 KB Output is correct
34 Correct 319 ms 53416 KB Output is correct
35 Correct 426 ms 75232 KB Output is correct
36 Correct 311 ms 53444 KB Output is correct
37 Correct 225 ms 34500 KB Output is correct
38 Correct 199 ms 29936 KB Output is correct
39 Correct 176 ms 42760 KB Output is correct
40 Correct 156 ms 42740 KB Output is correct
41 Correct 131 ms 42640 KB Output is correct
42 Correct 162 ms 34900 KB Output is correct
43 Correct 155 ms 35000 KB Output is correct
44 Correct 418 ms 103288 KB Output is correct
45 Correct 262 ms 67652 KB Output is correct
46 Correct 115 ms 30020 KB Output is correct
47 Correct 269 ms 44808 KB Output is correct
48 Correct 139 ms 37844 KB Output is correct
49 Correct 120 ms 37828 KB Output is correct
50 Correct 307 ms 45800 KB Output is correct
51 Correct 122 ms 33220 KB Output is correct
52 Correct 317 ms 45432 KB Output is correct
53 Correct 133 ms 38440 KB Output is correct
54 Correct 248 ms 55404 KB Output is correct
55 Correct 245 ms 46404 KB Output is correct
56 Correct 203 ms 49264 KB Output is correct
57 Correct 191 ms 50884 KB Output is correct
58 Correct 210 ms 52880 KB Output is correct
59 Correct 247 ms 52908 KB Output is correct
60 Correct 8 ms 14412 KB Output is correct
61 Correct 9 ms 14412 KB Output is correct
62 Correct 9 ms 14412 KB Output is correct
63 Correct 9 ms 14412 KB Output is correct
64 Correct 384 ms 65916 KB Output is correct
65 Incorrect 354 ms 49236 KB Output isn't correct
66 Halted 0 ms 0 KB -