Submission #436035

#	Time	Username	Problem	Language	Result	Execution time	Memory
436035		79brue	Keys (IOI21_keys)	C++17	100 / 100	1515 ms	140728 KiB

keys

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

struct disjointSet{
    int n;
    int par[300002];
    int sz[300002];

    void init(int _n){
        n = _n;
        for(int i=0; i<=n; i++) par[i] = i, sz[i] = 1;
    }

    int find(int x){
        if(x == par[x]) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        sz[x] += sz[y];
        par[y] = x;
    }
} dsu;

struct Bitset{
    unordered_map<int, ll> mp;
    Bitset(){}
    Bitset(int x){
        mp[x>>6] = 1ULL << (x&63);
    }

    void merge(Bitset &r){
        if(mp.size() > r.mp.size()){
            for(auto p: r.mp){
                mp[p.first] |= p.second;
            }
            r.mp.clear();
        }
        else{
            for(auto p: mp){
                r.mp[p.first] |= p.second;
            }
            mp.clear();
            mp.swap(r.mp);
        }
    }

    bool chk(int x){
        return !!(mp[x>>6] & (1ULL << (x&63)));
    }
};

int n;
Bitset arr[300002];
vector<pair<int, int> > link[300002];
stack<int> stk;
bool visited[300002];
bool merged[300002];

vector<int> sccVec;

void dfs1(int x){
    visited[x] = 1;
    for(auto &y: link[x]){
        y.first = dsu.find(y.first);
        if(visited[y.first] || !arr[x].chk(y.second)) continue;
        dfs1(y.first);
    }
    stk.push(x);
}

void dfs2(int x){
    visited[x] = 0;
    sccVec.push_back(x);
    for(auto &y: link[x]){
        y.first = dsu.find(y.first);
        if(!visited[y.first] || !arr[y.first].chk(y.second)) continue;
        dfs2(y.first);
    }
}

void makeSCC(){
    for(int i=0; i<n; i++){
        if(!visited[i] && !merged[i]) dfs1(i);
    }
    while(!stk.empty()){
        int tmp = stk.top();
        stk.pop();
        if(!visited[tmp]) continue;
        sccVec.clear();
        dfs2(tmp);

        for(auto x: sccVec){
            if(x==tmp) continue;
            arr[tmp].merge(arr[x]);

            if(link[tmp].size() > link[x].size()){
                for(auto p: link[x]) link[tmp].push_back(p);
                link[x].clear();
                link[x].shrink_to_fit();
            }
            else{
                for(auto p: link[tmp]) link[x].push_back(p);
                link[tmp].clear();
                link[tmp].shrink_to_fit();
                link[x].swap(link[tmp]);
            }
            dsu.merge(tmp, x);
            merged[x] = 1;
        }
    }
}

bool toOther[300002];

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c){
    n = (int)r.size();
    for(int i=0; i<n; i++){
        arr[i] = Bitset(r[i]);
    }
    for(int i=0; i<(int)u.size(); i++){
        link[u[i]].push_back(make_pair(v[i], c[i]));
        link[v[i]].push_back(make_pair(u[i], c[i]));
    }

    dsu.init(n);
    for(int d=0; d<=2; d++){
        makeSCC();
    }

    for(int i=0; i<n; i++){
        if(merged[i]) continue;
        for(auto y: link[i]){
            if(i != dsu.find(y.first) && arr[i].chk(y.second)) toOther[i] = 1;
        }
    }

    int minSize = n+1;
    for(int i=0; i<n; i++){
        if(!toOther[dsu.find(i)]) minSize = min(minSize, dsu.sz[dsu.find(i)]);
    }

    vector<int> ans (n);
    for(int i=0; i<n; i++){
        ans[i] = (!toOther[dsu.find(i)] && dsu.sz[dsu.find(i)] == minSize);
    }
    return ans;
}

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