oj.uz

Submission #803017

# Submission time Handle Problem Language Result Execution time Memory
803017 2023-08-02T18:18:00 Z thimote75 Worst Reporter 4 (JOI21_worst_reporter4) C++14
79 / 100
 453 ms 121748 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;
using Point = pair<int, int>;
using idata = vector<int>;
using igrid = vector<idata>;
using bdata = vector<bool>;

struct Node {
    int pos, delta, rng;

    int ssize = 1;
    int sdelt = 0;

    Node* left = nullptr; Node* right = nullptr;
    void compute () {
        ssize = 1;
        sdelt = delta;

        if (left != nullptr) {
            ssize += left->ssize;
            sdelt += left->sdelt;
        }
        if (right != nullptr) {
            ssize += right->ssize;
            sdelt += right->sdelt;
        }
    }
};

struct Treap {
    Node* root = nullptr;
    static void __show (Node* node, int depth) {
        if (node == nullptr) {
            for (int i = 0; i < depth; i ++) cout << " ";
            cout << ">\n";
            return ;
        }

        for (int i = 0; i < depth; i ++) cout << " ";
        cout << "> " << node->pos << " " << node->delta << " " << node->ssize << " " << node->sdelt << endl;

        __show(node->left, depth + 1);
        __show(node->right, depth + 1);
    }
    void show () {
        __show(root, 0);
    }

    static Node* __merge (Node* A, Node* B) {
        if (A == nullptr) return B;
        if (B == nullptr) return A;

        if (A->rng >= B->rng) {
            A->right = __merge(A->right, B);
            A->compute();
            return A;
        } else {
            B->left = __merge(A, B->left);
            B->compute();
            return B;
        }
    }
    static pair<Node*, Node*> __split (Node* A, int k) {
        if (A == nullptr) return { nullptr, nullptr };

        if (A->pos > k) {
            const auto [LL, LR] = __split(A->left, k);
            
            A->left = LR;
            A->compute();
            return { LL, A };
        } else {
            const auto [RL, RR] = __split(A->right, k);

            A->right = RL;
            A->compute();
            return { A, RR };
        }
    }

    void insert( int pos, int delta ) {
        Node* node = new Node();

        node->pos = pos;
        node->delta = delta;
        node->rng = rand();
        node->sdelt = delta;

        const auto ldata = __split(root, pos - 1);
        Node* left  = ldata.first;
        const auto rdata = __split(ldata.second, pos);
        Node* right = rdata.second;
        Node* mid   = rdata.first;

        if (mid == nullptr) mid = node;
        else {
            delete node;
            mid->delta += delta;
            mid->sdelt += delta;
        }

        root = __merge(left, __merge(mid, right));
    }
    int query (int x) {
        Node* local = root;

        int res = 0;
        while (local != nullptr) {
            if (local->pos > x) local = local->left;
            else {
                res += local->delta;
                if (local->left != nullptr) res += local->left->sdelt;
            
                local = local->right;
            }
        }

        return res;
    }
    void __chmin (Node* node, int until) {
        if (node == nullptr) return ;

        if (node->left != nullptr) {
            if (node->left->sdelt > until) {
                __chmin(node->left, until);
                node->right = nullptr;
                node->delta = 0;
                node->compute();
                return ;
            } else until -= node->left->sdelt;
        }

        if (until < node->delta) {
            node->delta = until;
            node->right = nullptr;
            node->compute();
            return ;
        }
        until -= node->delta;

        __chmin(node->right, until);
        node->compute();
    }
    void chmin (int until) {
        __chmin(root, until);
    }

    Treap cut (int position) {
        const auto data = __split(root, position);

        root = data.first;

        Treap other; other.root = data.second;
        return other;
    }

    static void __traverse (Node* node, vector<Node*> &answer) {
        if (node == nullptr) return ;
        __traverse(node->left,  answer);
        answer.push_back(node);
        __traverse(node->right, answer);
    }
    vector<Node*> traverse () {
        vector<Node*> ans;
        __traverse(root, ans);

        return ans;
    }

    int size () { return root != nullptr ? root->ssize : 0; }
    void swap (Treap &other) {
        Node* c = root;
        root = other.root;
        other.root = c;
    }
};

void compile (Treap &treap, int H_i, int C_i) {
    int chmin_left = treap.query( H_i );
    Treap right = treap.cut(H_i);

    right.insert( H_i + 1, C_i );

    treap.insert( - 1e9, C_i );
    treap.chmin( chmin_left );
    
    treap.root = treap.__merge(treap.root, right.root);
}

void merge (Treap &target, Treap &other) {
    if (target.size() < other.size())
        target.swap(other);
    
    for (Node* node : other.traverse())
        target.insert(node->pos, node->delta);
}

vector<Treap> treapArray;

idata A, H, C;

bdata isInCycle; idata depth;
idata cycleId; int __cyId = 0; igrid roads;
bdata visited, visiting; idata tp_sort;
bdata visitedSort;

void dfs_sort (int node) {
    if (visitedSort[node]) return ;
    visitedSort[node] = true;

    for (int next : roads[node]) dfs_sort(next);

    tp_sort.push_back(node);
}

int dfs_cycle (int node, int _depth) {
    if (visiting[node])
        return _depth - depth[node];
    if (visited[node]) return 0;

    visiting[node] = true;
    visited[node] = true;

    int res = dfs_cycle(A[node], _depth + 1);
    if (res != 0) {
        isInCycle[node] = true;
        cycleId[node] = __cyId;
    }
    if (res == 1) __cyId ++;

    visiting[node] = false;
    return max(res - 1, 0ll);
}

vector<vector<Point>> cycleIndices;
vector<Treap> cycleTreaps;

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    treapArray.resize(N);

    A.resize(N); H.resize(N); C.resize(N);
    for (int i = 0; i < N; i ++) {
        cin >> A[i] >> H[i] >> C[i];
        A[i] --;
    }
    visited  .resize(N);
    visiting .resize(N);
    isInCycle.resize(N);
    depth.resize(N);
    roads.resize(N);
    cycleId.resize(N);
    for (int i = 0; i < N; i ++)
        dfs_cycle(i, 0);
    
    visitedSort.resize(N);
    roads.resize(N);
    for (int i = 0; i < N; i ++)
        roads[A[i]].push_back(i);
    for (int i = 0; i < N; i ++)
        dfs_sort(i);
    
    for (int i : tp_sort) {
        if (isInCycle[i]) continue ;
        compile(treapArray[i], H[i], C[i]);

        merge(treapArray[A[i]], treapArray[i]);
    }

    cycleIndices.resize(__cyId);
    cycleTreaps.resize(__cyId);
    for (int i = 0; i < N; i ++) {
        if (!isInCycle[i]) continue ;

        cycleIndices[cycleId[i]].push_back({ H[i], C[i] });
        cycleTreaps[cycleId[i]].insert(H[i], 0);
        merge(cycleTreaps[cycleId[i]], treapArray[i]);
    }

    int res = 0;
    for (int iC = 0; iC < __cyId; iC ++) {
        map<int, int> no_cost;

        int lst = -2;
        int cnt = 0;
        int r = 0;
        sort(cycleIndices[iC].begin(), cycleIndices[iC].end());
        for (const auto &p : cycleIndices[iC]) {
            r += p.second;

            if (p.first == lst) {
                cnt += p.second;
            } else {
                if (lst != -2)
                    no_cost.insert({ lst, cnt });
                lst = p.first;
                cnt = p.second;
            }
        }
        if (lst != -2) {
            no_cost.insert({ lst, cnt });
        }

        int rmv = 1e18;
        for (Node* node : cycleTreaps[iC].traverse()) {
            int lmv = cycleTreaps[iC].query(node->pos) + r;
            if (no_cost.find(node->pos) != no_cost.end())
                lmv -= (*no_cost.find(node->pos)).second;
            
            rmv = min(rmv, lmv);
        }

        res += rmv;
    }

    cout << res << endl;
}

Compilation message

worst_reporter2.cpp: In static member function 'static std::pair<Node*, Node*> Treap::__split(Node*, long long int)':
worst_reporter2.cpp:70:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |             const auto [LL, LR] = __split(A->left, k);
      |                        ^
worst_reporter2.cpp:76:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |             const auto [RL, RR] = __split(A->right, k);
      |                        ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 2264 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 4 ms 1364 KB Output is correct
8 Correct 7 ms 2260 KB Output is correct
9 Correct 5 ms 1620 KB Output is correct
10 Correct 4 ms 1360 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 6 ms 1492 KB Output is correct
13 Correct 3 ms 1236 KB Output is correct
14 Correct 4 ms 1364 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 8 ms 2772 KB Output is correct
17 Correct 6 ms 1876 KB Output is correct
18 Correct 3 ms 1108 KB Output is correct
19 Correct 5 ms 1620 KB Output is correct
20 Correct 4 ms 1236 KB Output is correct
21 Correct 3 ms 1236 KB Output is correct
22 Correct 5 ms 1876 KB Output is correct
23 Correct 4 ms 1492 KB Output is correct
24 Correct 5 ms 1740 KB Output is correct
25 Correct 4 ms 1356 KB Output is correct
26 Correct 4 ms 1620 KB Output is correct
27 Correct 5 ms 1740 KB Output is correct
28 Correct 5 ms 1620 KB Output is correct
29 Correct 4 ms 1620 KB Output is correct
30 Correct 6 ms 1604 KB Output is correct
31 Correct 6 ms 1620 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 2264 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 4 ms 1364 KB Output is correct
8 Correct 7 ms 2260 KB Output is correct
9 Correct 5 ms 1620 KB Output is correct
10 Correct 4 ms 1360 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 6 ms 1492 KB Output is correct
13 Correct 3 ms 1236 KB Output is correct
14 Correct 4 ms 1364 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 8 ms 2772 KB Output is correct
17 Correct 6 ms 1876 KB Output is correct
18 Correct 3 ms 1108 KB Output is correct
19 Correct 5 ms 1620 KB Output is correct
20 Correct 4 ms 1236 KB Output is correct
21 Correct 3 ms 1236 KB Output is correct
22 Correct 5 ms 1876 KB Output is correct
23 Correct 4 ms 1492 KB Output is correct
24 Correct 5 ms 1740 KB Output is correct
25 Correct 4 ms 1356 KB Output is correct
26 Correct 4 ms 1620 KB Output is correct
27 Correct 5 ms 1740 KB Output is correct
28 Correct 5 ms 1620 KB Output is correct
29 Correct 4 ms 1620 KB Output is correct
30 Correct 6 ms 1604 KB Output is correct
31 Correct 6 ms 1620 KB Output is correct
32 Correct 7 ms 2260 KB Output is correct
33 Correct 387 ms 91648 KB Output is correct
34 Correct 269 ms 60328 KB Output is correct
35 Correct 377 ms 88220 KB Output is correct
36 Correct 253 ms 60380 KB Output is correct
37 Correct 141 ms 38460 KB Output is correct
38 Correct 119 ms 32792 KB Output is correct
39 Correct 199 ms 44756 KB Output is correct
40 Correct 190 ms 37880 KB Output is correct
41 Correct 96 ms 32792 KB Output is correct
42 Correct 181 ms 40128 KB Output is correct
43 Correct 173 ms 34212 KB Output is correct
44 Correct 453 ms 121748 KB Output is correct
45 Correct 296 ms 76868 KB Output is correct
46 Correct 94 ms 32128 KB Output is correct
47 Correct 327 ms 52528 KB Output is correct
48 Correct 191 ms 37096 KB Output is correct
49 Correct 101 ms 36876 KB Output is correct
50 Correct 359 ms 58700 KB Output is correct
51 Correct 165 ms 43292 KB Output is correct
52 Correct 311 ms 53296 KB Output is correct
53 Correct 160 ms 37708 KB Output is correct
54 Correct 153 ms 47908 KB Output is correct
55 Correct 222 ms 53492 KB Output is correct
56 Correct 184 ms 50368 KB Output is correct
57 Correct 182 ms 49312 KB Output is correct
58 Correct 278 ms 49852 KB Output is correct
59 Correct 282 ms 49952 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 7 ms 2264 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 4 ms 1364 KB Output is correct
8 Correct 7 ms 2260 KB Output is correct
9 Correct 5 ms 1620 KB Output is correct
10 Correct 4 ms 1360 KB Output is correct
11 Correct 3 ms 1236 KB Output is correct
12 Correct 6 ms 1492 KB Output is correct
13 Correct 3 ms 1236 KB Output is correct
14 Correct 4 ms 1364 KB Output is correct
15 Correct 4 ms 1236 KB Output is correct
16 Correct 8 ms 2772 KB Output is correct
17 Correct 6 ms 1876 KB Output is correct
18 Correct 3 ms 1108 KB Output is correct
19 Correct 5 ms 1620 KB Output is correct
20 Correct 4 ms 1236 KB Output is correct
21 Correct 3 ms 1236 KB Output is correct
22 Correct 5 ms 1876 KB Output is correct
23 Correct 4 ms 1492 KB Output is correct
24 Correct 5 ms 1740 KB Output is correct
25 Correct 4 ms 1356 KB Output is correct
26 Correct 4 ms 1620 KB Output is correct
27 Correct 5 ms 1740 KB Output is correct
28 Correct 5 ms 1620 KB Output is correct
29 Correct 4 ms 1620 KB Output is correct
30 Correct 6 ms 1604 KB Output is correct
31 Correct 6 ms 1620 KB Output is correct
32 Correct 7 ms 2260 KB Output is correct
33 Correct 387 ms 91648 KB Output is correct
34 Correct 269 ms 60328 KB Output is correct
35 Correct 377 ms 88220 KB Output is correct
36 Correct 253 ms 60380 KB Output is correct
37 Correct 141 ms 38460 KB Output is correct
38 Correct 119 ms 32792 KB Output is correct
39 Correct 199 ms 44756 KB Output is correct
40 Correct 190 ms 37880 KB Output is correct
41 Correct 96 ms 32792 KB Output is correct
42 Correct 181 ms 40128 KB Output is correct
43 Correct 173 ms 34212 KB Output is correct
44 Correct 453 ms 121748 KB Output is correct
45 Correct 296 ms 76868 KB Output is correct
46 Correct 94 ms 32128 KB Output is correct
47 Correct 327 ms 52528 KB Output is correct
48 Correct 191 ms 37096 KB Output is correct
49 Correct 101 ms 36876 KB Output is correct
50 Correct 359 ms 58700 KB Output is correct
51 Correct 165 ms 43292 KB Output is correct
52 Correct 311 ms 53296 KB Output is correct
53 Correct 160 ms 37708 KB Output is correct
54 Correct 153 ms 47908 KB Output is correct
55 Correct 222 ms 53492 KB Output is correct
56 Correct 184 ms 50368 KB Output is correct
57 Correct 182 ms 49312 KB Output is correct
58 Correct 278 ms 49852 KB Output is correct
59 Correct 282 ms 49952 KB Output is correct
60 Correct 1 ms 312 KB Output is correct
61 Incorrect 1 ms 212 KB Output isn't correct
62 Halted 0 ms 0 KB -