Submission #589793

#	Time	Username	Problem	Language	Result	Execution time	Memory
589793		PiejanVDC	Keys (IOI21_keys)	C++17	67 / 100	3069 ms	130364 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN = (int)3e5 + 5;

vector<set<int>>keys(mxN);
vector<vector<int>>component(mxN);

set<pair<int,int>>original_adj[mxN];
vector<int>build_adj[mxN];
vector<int>rev_build_adj[mxN];

// SCC

int comp;

bool SCC_vis[mxN];
bool COLOR_vis[mxN];

deque<int>SCC_list;

vector<int>final_color(mxN);

void SCC_dfs(int u) {
    SCC_vis[u] = 1;

    for(auto z : build_adj[u]) if(!SCC_vis[z]) {
        SCC_dfs(z);
    }

    SCC_list.push_front(u);
}

int current_color;

void SCC_color(int u) {
    COLOR_vis[u] = 1;
    final_color[u] = current_color;
    component[current_color].push_back(u);
    
    for(auto z : rev_build_adj[u]) if(!COLOR_vis[z]) {
        SCC_color(z);
    }
}

void SCC(int N) {
    for(int i = 0 ; i < N ; i++) {
        component[i].clear();
        keys[i].clear();
    }

    comp = 0;

    memset(SCC_vis, 0, sizeof(SCC_vis));
    memset(COLOR_vis, 0, sizeof(COLOR_vis));
    SCC_list.clear();

    for(int i = 0 ; i < N ; i++) if(!SCC_vis[i]) {
        SCC_dfs(i);
    }

    current_color = 0;

    for(auto z : SCC_list) if(!COLOR_vis[z]) {
        comp++;
        SCC_color(z);
        current_color++;
    }

}

bool vis[mxN];

int sz;

bool dfs(int u, int col) {
    if(final_color[u] != col)
        return 0;
    
    vis[u] = 1;
    bool ok = 1;
    sz++;

    for(auto z : build_adj[u]) if(!vis[z]) {
        ok &= dfs(z, col);
    }
    
    return ok;
}

vector<int>find_reachable(vector<int>r, vector<int>u, vector<int>v, vector<int>c) {
    
    const int n = (int)r.size();
    const int m = (int)u.size();

    comp = n;

    // for each component:
        // merge all keys   
        // iterate over neighbours and add edges when possible

    // init

    for(int i = 0 ; i < m ; i++) {
        original_adj[u[i]].insert({v[i], c[i]});
        original_adj[v[i]].insert({u[i], c[i]});
    }

    for(int i = 0 ; i < n ; i++) {
        component[i].push_back(i);
    }

    for(int i_ = 0 ; i_ < log2(n) ; i_++) {

        for(int i = 0 ; i < comp ; i++) { // change to number of comps
            
            for(auto z : component[i]) {
                keys[i].insert(r[z]);
                //cout << i_ << ' ' << i << ' ' << z << '\n';
            }

            for(auto z : component[i]) {
                vector<pair<int,int>>del;
                for(auto e = original_adj[z].begin() ; e != original_adj[z].end() ; e++) {
                    if(keys[i].find(e->second) != keys[i].end()) {
                        //if(!i_) cout << "Added edge " << z << ' ' << e.first << '\n';
                        build_adj[z].push_back(e->first);
                        rev_build_adj[e->first].push_back(z);
                        del.push_back(*e);
                    }
                }
                for(auto d : del)
                    original_adj[z].erase(original_adj[z].find(d));
            }

        }

        SCC(n);

    }

    int mn = INT_MAX;

    vector<int>answer(n,0);

    for(int i = 0 ; i < comp ; i++) { // change to nr of comps

        sz = 0;

        if(dfs(component[i][0], i)) {
            if(sz == mn) {
                for(auto z : component[i])
                    answer[z] = 1;
            } else if(sz < mn) {
                mn = sz;
                answer.clear();
                answer.resize(n,0);
                for(auto z : component[i])
                    answer[z] = 1;
            }
        }

    }

    return answer;
}

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