Submission #1053007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053007		dozer	Keys (IOI21_keys)	C++17	37 / 100	3075 ms	125012 KiB

keys

#include "keys.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
//#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define pb push_back
#define pii pair<int, int>
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define st first
#define nd second
#define ll long long
#define LL node * 2
#define RR node * 2 + 1
#define N 300005


const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;

int par[N], sz[N], vis[N], vis2[N];
set<int> keys[N];
set<pii> edges[N];
set<int> adj[N], rev_adj[N]; //->{key, node}
vector<int> tomerge[N];
int SIZE;

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

void uni(int a, int b){
    a = find(a), b = find(b);
    if (a == b) return;
    SIZE--;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a;
    sz[a] += sz[b];
    
    if (keys[b].size() > keys[a].size()) keys[a].swap(keys[b]);
    for (auto i : keys[b]) keys[a].insert(i);

    if (edges[b].size() > edges[a].size()) edges[a].swap(edges[b]);
    for (auto i : edges[b]) edges[a].insert({i.st, find(i.nd)});

    if (adj[b].size() > adj[a].size()) adj[a].swap(adj[b]);
    for (auto i : adj[b]) adj[a].insert(i);

    if (rev_adj[b].size() > rev_adj[a].size()) rev_adj[a].swap(rev_adj[b]);
    for (auto i : rev_adj[b]) rev_adj[a].insert(i);
    
    for (auto i : keys[a]){
        auto it = edges[a].lower_bound({i, 0});
        while (it != edges[a].end() && it->st == i){
            pii tmp = *it;
            tmp.nd = find(tmp.nd);
            adj[a].insert(tmp.nd);
            rev_adj[tmp.nd].insert(a);
            it = edges[a].erase(it);
        }
    }
    
}

stack<int> s;

void dfs1(int node){
    vis[node] = 1;
    set<int> nw;

    for (auto i : adj[node]){
        int to = find(i);
        nw.insert(to);
        if (vis[to]) continue;
        dfs1(to);
    }
    s.push(node);
    adj[node] = nw;
}


void dfs2(int node, vector<int> &tmp){
    set<int> nw;
    vis2[node] = 1;    
    for (auto i : rev_adj[node]){
        int to = find(i);
        nw.insert(to);
        if (vis2[to]) continue;
        dfs2(to, tmp);
    }

    rev_adj[node] = nw;
    tmp.pb(node);
}


vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    int n = r.size();
    int m = u.size();
    for (int i = 0; i < n; i++){
        par[i] = i, sz[i] = 1;
        keys[i].insert(r[i]);
        adj[i].clear(), edges[i].clear(), rev_adj[i].clear();
    }

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

    for (int i = 0; i < n; i++){
        vector<pii> del;
        for (auto j : edges[i]){
            if (j.st == r[i]){
                adj[i].insert(j.nd);
                rev_adj[j.nd].insert(i);
                del.pb(j);
            }
        }

        for (auto j : del) edges[i].erase(j);
    }
    

    SIZE = n;

    int steps = 0;
    while(true){
        int prv = SIZE;
        for (int i = 0; i < n; i++)
            vis[i] = 0, vis2[i] = 0;
        for (int i = 0; i < n; i++){
            if (vis[i] == 0 && par[i] == i) dfs1(i);
        }

        
        while(!s.empty()){
            int top = s.top();
            s.pop();
            if (vis2[top]) continue;
            vector<int> tmp;
            dfs2(top, tomerge[top]);
        }

        for (int i = 0; i < n; i++){
            for (auto j : tomerge[i]) uni(i, j);
            tomerge[i].clear();
        }
        if (prv == SIZE) break;
    }

    queue<int> q;
    for (int i = 0; i < n; i++){
        if (par[i] != i) continue;
        set<int> tmp;
        for (auto j : adj[i]) tmp.insert(find(j));
        tmp.erase(i);
        adj[i] = tmp;
        tmp.clear();
        for (auto j : rev_adj[i]) tmp.insert(find(j));
        tmp.erase(i);
        rev_adj[i] = tmp;
    }

    for (int i = 0; i < n; i++)
        if (par[i] == i && adj[i].empty()) q.push(i);

    while(!q.empty()){
        int top = q.front();
        q.pop();
        for (auto i : rev_adj[top]){
            sz[i] += sz[top];
            adj[i].erase(top);
            if (adj[i].empty()) q.push(i);
        }
    }
    
    vector<int> ans(r.size(), 0);
    int mini = n;
    for (int i = 0; i < n; i++) mini = min(mini, sz[find(i)]);
    for (int i = 0; i < n; i++) if (sz[find(i)] == mini) ans[i] = 1;
    return ans;
}

/*

int main() {
    fileio();
    int n, m;
    assert(2 == scanf("%d%d", &n, &m));
    std::vector<int> r(n), u(m), v(m), c(m);
    for(int i=0; i<n; i++) {
        assert(1 == scanf("%d", &r[i]));
    }
    for(int i=0; i<m; i++) {
        assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i]));
    }
    fclose(stdin);

    std::vector<int> ans = find_reachable(r, u, v, c);

    for (int i = 0; i < (int) ans.size(); ++i) {
        if(i) putchar(' ');
        putchar(ans[i]+'0');
    }
    printf("\n");
    return 0;
}
*/

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:128:9: warning: unused variable 'steps' [-Wunused-variable]
  128 |     int steps = 0;
      |         ^~~~~

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