Submission #979410

#	Time	Username	Problem	Language	Result	Execution time	Memory
979410		alontanay	Keys (IOI21_keys)	C++17	67 / 100	3100 ms	304148 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>

#define f first
#define s second
#define NEW_STATE 0
#define ACTIVE_STATE 1
#define OLD_STATE 2
#define NO_POS -1

using namespace std;
using pi = pair<int,int>;

const int MAX_N = 3e5+5;
namespace dsu {
    int sz[MAX_N], root[MAX_N], L[MAX_N];
    int PTR_pos[MAX_N];
    stack<int> pos[MAX_N];
    int PTR_ord_future[MAX_N];
    set<pi,greater<pi>> ord_future[MAX_N];
    void init(int n) {
        for(int i = 0; i < n; i ++) {
            sz[i] = 1;
            root[i] = i;
            PTR_pos[i] = i;
            PTR_ord_future[i] = i;
        }
    }
    int get_root(int node) {
        if(root[node] == node) {return node;}
        return root[node] = get_root(root[node]);
    }
    void add_pos(int node, int ne) {
        pos[PTR_pos[get_root(node)]].push(ne);
    }
    int poll_pos(int node) {
        int ptr = PTR_pos[get_root(node)];
        if(pos[ptr].empty()) { return NO_POS; }
        int top = pos[ptr].top();
        pos[ptr].pop();
        return top;
    }
    bool are_joined(int a, int b) {
        return get_root(a) == get_root(b);
    }
    int merge(int a, int b) {
        a = get_root(a);
        b = get_root(b);
        if(a == b) { return a; }
        if(sz[a] < sz[b]) {
            swap(a,b);
        }
        L[a] = min(L[a],L[b]);
        root[b] = a;
        {
            int big_ptr = PTR_pos[a];
            int small_ptr = PTR_pos[b];
            if(pos[big_ptr].size() < pos[small_ptr].size()) {
                swap(big_ptr,small_ptr);
            }
            PTR_pos[a] = big_ptr;
            stack<int> &big_pos = pos[big_ptr];
            stack<int> &small_pos = pos[small_ptr];
            while(!small_pos.empty()) {
                big_pos.push(small_pos.top());
                small_pos.pop();
            }
        }
        {
            int big_ptr = PTR_ord_future[a];
            int small_ptr = PTR_ord_future[b];
            if(ord_future[big_ptr].size() < ord_future[small_ptr].size()) {
                swap(big_ptr,small_ptr);
            }
            PTR_ord_future[a] = big_ptr;
            set<pi,greater<pi>> &big_ord_future = ord_future[big_ptr];
            set<pi,greater<pi>> &small_ord_future = ord_future[small_ptr];
            big_ord_future.insert(small_ord_future.begin(),small_ord_future.end());
            small_ord_future.clear();
            while(!big_ord_future.empty() && big_ord_future.begin()->f >= L[a]) {
                pos[PTR_pos[a]].push(big_ord_future.begin()->s);
                big_ord_future.erase(big_ord_future.begin());
            }
        }
        return a;
    }
}

vector<pi> nei[MAX_N];
vector<pi> need_key[MAX_N];
int state[MAX_N];
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
    int n = r.size(), m = u.size();
    dsu::init(n);
    for(int i = 0;i < m; i ++) {
        int a = u[i], b = v[i], t = c[i];
        nei[a].push_back({b,t});
        nei[b].push_back({a,t});
    }
    vector<int> last_occ(n);
    int cidx = 0;
    vector<int> res;
    int opt_score = n;
    for(int i = 0; i < n; i ++) {
        if(state[i] != NEW_STATE) { continue; }
        stack<int> UPD_need_key;
        stack<int> reached_nodes;
        bool reached_old = false;
        int node = i;
        stack<int> comp_stack;
        while(true) {
            cidx++;

            reached_nodes.push(node);
            int key = r[node];
            dsu::L[node] = cidx;
            comp_stack.push(node);
            last_occ[key] = cidx;
            state[node] = ACTIVE_STATE;
            for(auto &[ne, req] : nei[node]) {
                UPD_need_key.push(req);
                need_key[req].push_back({node,ne});
                dsu::ord_future[node].insert({last_occ[req],ne});
            }
            for(pi edge : need_key[key]) {
                dsu::add_pos(edge.f,edge.s);
            }
            need_key[key].clear();

            int next_node;
            bool converged = false;
            while(true) {
                next_node = dsu::poll_pos(node);
                if(next_node == NO_POS) {
                    converged = true;
                    break;
                }
                if(state[next_node] == OLD_STATE) {
                    reached_old = true;
                    break;
                }
                if(state[next_node] == NEW_STATE) {
                    break;
                }

                while(comp_stack.size() >= 2 && !dsu::are_joined(node,next_node)) {
                    int top = comp_stack.top();
                    comp_stack.pop();
                    int bef = comp_stack.top();
                    comp_stack.pop();
                    int new_root = dsu::merge(top,bef);
                    comp_stack.push(new_root);
                }
            }
            if(reached_old || converged) {
                break;
            }
            node = next_node;
        }
        vector<int> base_comp;
        base_comp.reserve(reached_nodes.size());
        while(!reached_nodes.empty()) {
            int top = reached_nodes.top();
            if(!reached_old && dsu::are_joined(node, top)) {
                base_comp.push_back(top);
            }
            reached_nodes.pop();
            state[top] = OLD_STATE;
        }
        if(!reached_old) {
            int score = base_comp.size();
            if(score < opt_score) {
                opt_score = score;
                res.clear();
            }
            if(score == opt_score) {
                res.insert(res.begin(),base_comp.begin(),base_comp.end());
            }
        }
        while(!UPD_need_key.empty()) {
            int key = UPD_need_key.top();
            UPD_need_key.pop();
            need_key[key].clear();
        }
    }
    vector<int> ans(n);
    for(int r : res) {
        ans[r] = 1;
    }
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 30 / 30
• Subtask 5: 0 / 33