Submission #803017

#	Time	Username	Problem	Language	Result	Execution time	Memory
803017		thimote75	Worst Reporter 4 (JOI21_worst_reporter4)	C++14	79 / 100	453 ms	121748 KiB

worst_reporter2

#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 (stderr)

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 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21