oj.uz

Submission #726058

# Submission time Handle Problem Language Result Execution time Memory
726058 2023-04-18T12:04:19 Z piOOE Worst Reporter 4 (JOI21_worst_reporter4) C++17
14 / 100
 1089 ms 444404 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N_ = 2e5 * 20 * 2 + 1;
int top = 1;

struct Node {
    ll sum = 0, mxp = 0;
    int left = 0, right = 0;
} t[N_];

int create() {
    return top++;
}

void pull(int x) {
    int l = t[x].left, r = t[x].right;
    t[x].sum = t[l].sum + t[r].sum;
    t[x].mxp = max(t[l].mxp, t[l].sum + t[r].mxp);
}

void modify(int x, int lx, int rx, int i, ll d) {
    if (lx == i && rx == i + 1) {
        t[x].sum += d;
        t[x].mxp = max(t[x].sum, 0LL);
        return;
    }

    int mid = (lx + rx) >> 1;

    if (i < mid) {
        if (t[x].left == 0) {
            t[x].left = create();
        }
        modify(t[x].left, lx, mid, i, d);
    } else {
        if (t[x].right == 0) {
            t[x].right = create();
        }
        modify(t[x].right, mid, rx, i, d);
    }

    pull(x);
}

constexpr int N = 2e5 + 1;

vector<int> adj[N], inside[N];

int fa[N], n;

void initFa() {
    iota(fa, fa + n + 1, 0);
    for (int i = 0; i < n; ++i) {
        inside[i] = {i};
    }
}

int leader(int x) {
    while (x != fa[x]) {
        x = fa[x] = fa[fa[x]];
    }
    return x;
}

void unite(int x, int y) {
    x = leader(x), y = leader(y);
    if (x == y) {
        return;
    }

    if (inside[x].size() < inside[y].size()) {
        swap(inside[x], inside[y]);
    }
    inside[x].insert(inside[x].end(), inside[y].begin(), inside[y].end());
    inside[y].clear();

    fa[y] = x;
}

int yy[N], h[N], H[N], C[N], siz[N], root[N];
int m = 0;

pair<ll, ll> getBest(int x, int i) {
    int lx = 0, rx = m;
    ll ans = 0, sum = 0;
    while (lx + 1 < rx) {
        int mid = lx + rx >> 1;
        if (i < mid) {
            ans = max(ans, t[t[x].right].mxp + t[t[x].left].sum + sum);
            rx = mid;
            x = t[x].left;
        } else {
            sum += t[t[x].left].sum;
            lx = mid;
            x = t[x].right;
        }
    }
    sum += t[x].sum;
    ans = max(ans, sum);
    return {ans, sum};
}

void modify(int x, int l, int r, ll d) {
    if (l < m) {
        modify(x, 0, m, l, d);
    }
    if (r < m) {
        modify(x, 0, m, r, -d);
    }
}

void addDP(int x, int i, ll dp) {
    auto [ans, sum] = getBest(x, i);
    ans += dp;
    assert(ans >= sum);
    modify(x, i, i + 1, ans - sum);
}


void upd(int x, int i) {
    addDP(x, i, 0);
}

void dfs(int v) {
    sort(inside[v].begin(), inside[v].end(), [&](int i, int j) {
        return H[i] < H[j];
    });

    vector<int> ours = inside[v];

    siz[v] = inside[v].size();

    for (int to: adj[v]) {
        dfs(to);
        siz[v] += siz[to];
    }

    sort(adj[v].begin(), adj[v].end(), [&](int x, int y) {
        return siz[x] > siz[y];
    });

    if (adj[v].empty()) {
        root[v] = create();
    } else {
        root[v] = root[adj[v][0]];
        unite(v, adj[v][0]);
    }

//    for (int i = 0; i < m; ++i) {
//        upd(root[v], i);
//    }

//    if (v == 3) {
//        cout << "as" << endl;
//    }

    auto fuck = [&](int l, int r, ll dp) {
        upd(root[v], l);
        upd(root[v], r - 1);
        modify(root[v], l, r, dp);
    };

    for (int i = 1; i < adj[v].size(); ++i) {
        int to = adj[v][i];

//        if (v == 0) {
//            cout << "here" << endl;
//        }

        sort(inside[to].begin(), inside[to].end(), [&](int x, int y) {
            return H[x] < H[y];
        });

        for (int x = 0; x < inside[to].size(); ++x) {
            int l = x == 0 ? 0 : h[inside[to][x - 1]] + 1;
            int r = h[inside[to][x]] + 1;
            ll dp = getBest(root[to], h[inside[to][x]]).first;
            fuck(l, r, dp);
        }

        unite(v, to);
    }

    for (int i = 0, j = 0; i < ours.size(); i = j) {
        ll sum = 0;
        while (j < ours.size() && H[ours[i]] == H[ours[j]]) {
            sum += C[ours[j]];
            j += 1;
        }
        addDP(root[v], h[ours[i]], sum);
    }

//    for (int i = 0; i < m; ++i) {
//        upd(root[v], i);
//    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    vector<int> p(n);

    for (int i = 0; i < n; ++i) {
        cin >> p[i] >> H[i] >> C[i];
        p[i] -= 1;
    }

    copy(H, H + n, yy);

    sort(yy, yy + n);
    m = unique(yy, yy + n) - yy;

    for (int i = 0; i < n; ++i) {
        h[i] = lower_bound(yy, yy + m, H[i]) - yy;
    }

    vector<int> used(n);
    initFa();
    int T = 0;

    for (int i = 0; i < n; ++i) {
        if (used[i]) {
            continue;
        }

        int x = i;
        ++T;
        vector<int> now;

        while (!used[x]) {
            now.push_back(x);
            used[x] = T;
            x = p[x];
        }

        if (used[x] == T) {
            int y = p[x];
            while (y != x) {
                unite(x, y);
                y = p[y];
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        if (leader(i) == i) {
            int x = leader(p[i]);
            if (x == i) {
                adj[n].push_back(i);
//                cout << n << "->" << i << endl;
            } else {
                adj[x].push_back(i);
//                cout << x << "->" << i << endl;
            }
        }
    }

    dfs(n);

    ll ans = getBest(root[n], 0).first;

//    cout << ans << endl;

    ans = accumulate(C, C + n, 0LL) - ans;

    cout << ans << '\n';


    return 0;
}

Compilation message

worst_reporter2.cpp: In function 'std::pair<long long int, long long int> getBest(int, int)':
worst_reporter2.cpp:90:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |         int mid = lx + rx >> 1;
      |                   ~~~^~~~
worst_reporter2.cpp: In function 'void dfs(int)':
worst_reporter2.cpp:166:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     for (int i = 1; i < adj[v].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
worst_reporter2.cpp:177:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |         for (int x = 0; x < inside[to].size(); ++x) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:187:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |     for (int i = 0, j = 0; i < ours.size(); i = j) {
      |                            ~~^~~~~~~~~~~~~
worst_reporter2.cpp:189:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |         while (j < ours.size() && H[ours[i]] == H[ours[j]]) {
      |                ~~^~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9732 KB Output is correct
5 Correct 29 ms 14228 KB Output is correct
6 Correct 17 ms 11712 KB Output is correct
7 Correct 12 ms 10896 KB Output is correct
8 Correct 26 ms 14480 KB Output is correct
9 Correct 18 ms 11804 KB Output is correct
10 Correct 12 ms 10956 KB Output is correct
11 Correct 9 ms 10396 KB Output is correct
12 Correct 12 ms 11476 KB Output is correct
13 Correct 12 ms 11292 KB Output is correct
14 Correct 13 ms 11280 KB Output is correct
15 Correct 11 ms 10836 KB Output is correct
16 Correct 37 ms 16728 KB Output is correct
17 Correct 22 ms 12372 KB Output is correct
18 Correct 9 ms 10452 KB Output is correct
19 Correct 13 ms 11880 KB Output is correct
20 Correct 11 ms 11308 KB Output is correct
21 Correct 9 ms 10964 KB Output is correct
22 Correct 14 ms 12244 KB Output is correct
23 Correct 11 ms 11348 KB Output is correct
24 Correct 12 ms 11844 KB Output is correct
25 Correct 11 ms 11280 KB Output is correct
26 Correct 10 ms 11536 KB Output is correct
27 Correct 15 ms 11948 KB Output is correct
28 Correct 13 ms 11732 KB Output is correct
29 Correct 11 ms 11604 KB Output is correct
30 Correct 13 ms 11156 KB Output is correct
31 Correct 12 ms 11220 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9732 KB Output is correct
5 Correct 29 ms 14228 KB Output is correct
6 Correct 17 ms 11712 KB Output is correct
7 Correct 12 ms 10896 KB Output is correct
8 Correct 26 ms 14480 KB Output is correct
9 Correct 18 ms 11804 KB Output is correct
10 Correct 12 ms 10956 KB Output is correct
11 Correct 9 ms 10396 KB Output is correct
12 Correct 12 ms 11476 KB Output is correct
13 Correct 12 ms 11292 KB Output is correct
14 Correct 13 ms 11280 KB Output is correct
15 Correct 11 ms 10836 KB Output is correct
16 Correct 37 ms 16728 KB Output is correct
17 Correct 22 ms 12372 KB Output is correct
18 Correct 9 ms 10452 KB Output is correct
19 Correct 13 ms 11880 KB Output is correct
20 Correct 11 ms 11308 KB Output is correct
21 Correct 9 ms 10964 KB Output is correct
22 Correct 14 ms 12244 KB Output is correct
23 Correct 11 ms 11348 KB Output is correct
24 Correct 12 ms 11844 KB Output is correct
25 Correct 11 ms 11280 KB Output is correct
26 Correct 10 ms 11536 KB Output is correct
27 Correct 15 ms 11948 KB Output is correct
28 Correct 13 ms 11732 KB Output is correct
29 Correct 11 ms 11604 KB Output is correct
30 Correct 13 ms 11156 KB Output is correct
31 Correct 12 ms 11220 KB Output is correct
32 Correct 25 ms 14384 KB Output is correct
33 Runtime error 1089 ms 444404 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 ms 9732 KB Output is correct
5 Correct 29 ms 14228 KB Output is correct
6 Correct 17 ms 11712 KB Output is correct
7 Correct 12 ms 10896 KB Output is correct
8 Correct 26 ms 14480 KB Output is correct
9 Correct 18 ms 11804 KB Output is correct
10 Correct 12 ms 10956 KB Output is correct
11 Correct 9 ms 10396 KB Output is correct
12 Correct 12 ms 11476 KB Output is correct
13 Correct 12 ms 11292 KB Output is correct
14 Correct 13 ms 11280 KB Output is correct
15 Correct 11 ms 10836 KB Output is correct
16 Correct 37 ms 16728 KB Output is correct
17 Correct 22 ms 12372 KB Output is correct
18 Correct 9 ms 10452 KB Output is correct
19 Correct 13 ms 11880 KB Output is correct
20 Correct 11 ms 11308 KB Output is correct
21 Correct 9 ms 10964 KB Output is correct
22 Correct 14 ms 12244 KB Output is correct
23 Correct 11 ms 11348 KB Output is correct
24 Correct 12 ms 11844 KB Output is correct
25 Correct 11 ms 11280 KB Output is correct
26 Correct 10 ms 11536 KB Output is correct
27 Correct 15 ms 11948 KB Output is correct
28 Correct 13 ms 11732 KB Output is correct
29 Correct 11 ms 11604 KB Output is correct
30 Correct 13 ms 11156 KB Output is correct
31 Correct 12 ms 11220 KB Output is correct
32 Correct 25 ms 14384 KB Output is correct
33 Runtime error 1089 ms 444404 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -