Submission #478894

#	Time	Username	Problem	Language	Result	Execution time	Memory
478894		couplefire	Keys (IOI21_keys)	C++17	100 / 100	2905 ms	167808 KiB

keys

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

const int N = 300005;

int n, m, r[N], u[N], v[N], c[N], fa1[N], fa2[N], siz[N], nxt[N];
set<int> good_keys[N];
map<int, vector<int>> bad_edges[N];
vector<int> good_edges[N];

int find1(int v){return v==fa1[v]?v:fa1[v]=find1(fa1[v]);}

int find2(int v){return v==fa2[v]?v:fa2[v]=find2(fa2[v]);}

void unite1(int u, int v){
    u = find1(u), v = find1(v);
    if(u==v) return;
    fa1[u] = v;
}

void unite2(int u, int v){
    u = find2(u), v = find2(v);
    if(u==v) return;
    fa2[u] = v; siz[v] += siz[u];
    good_edges[v].insert(good_edges[v].end(), good_edges[u].begin(), good_edges[u].end());
    for(auto x : good_keys[u]){
        good_keys[v].insert(x);
        if(bad_edges[v].count(x)){
            good_edges[v].insert(good_edges[v].end(), bad_edges[v][x].begin(), bad_edges[v][x].end());
            bad_edges[v].erase(x);
        }
    }
    for(auto [x, y] : bad_edges[u])
        if(good_keys[v].count(x))
            good_edges[v].insert(good_edges[v].end(), y.begin(), y.end());
        else
            bad_edges[v][x].insert(bad_edges[v][x].begin(), y.begin(), y.end()); 
}

vector<int> find_reachable(vector<int> _r, vector<int> _u, vector<int> _v, vector<int> _c){
    n = _r.size(), m = _u.size();
    for(int i = 0; i<n; ++i)
        r[i] = _r[i];
    for(int i = 0; i<m; ++i)
        u[i] = _u[i], v[i] = _v[i], c[i] = _c[i];
    vector<int> res(n, 0);
    priority_queue<pair<int, int>> todo;
    for(int i = 0; i<n; ++i)
        todo.push({good_edges[i].size(), i});
    iota(fa1, fa1+n, 0);
    iota(fa2, fa2+n, 0);
    memset(nxt, -1, sizeof nxt);
    fill(siz, siz+n, 1);
    for(int i = 0; i<n; ++i)
        good_keys[i].insert(r[i]);
    for(int i = 0; i<m; ++i){
        if(c[i]!=r[u[i]]) bad_edges[u[i]][c[i]].push_back(v[i]);
        else good_edges[u[i]].push_back(v[i]);
        if(c[i]!=r[v[i]]) bad_edges[v[i]][c[i]].push_back(u[i]);
        else good_edges[v[i]].push_back(u[i]);
    }
    while(!todo.empty()){
        int cur = todo.top().second; todo.pop();
        cur = find2(cur);
        if(good_edges[cur].empty() || nxt[cur]>=0) continue;
        int to = good_edges[cur].back(); to = find2(to);
        good_edges[cur].pop_back();
        if(cur==to){
            todo.push({good_edges[cur].size(), cur});
            continue;
        }
        if(find1(cur)!=find1(to)){
            nxt[cur] = to;
            unite1(cur, to);
            continue;
        }
        while(to!=cur){
            unite2(to, cur);
            to = find2(nxt[to]);
        } nxt[cur] = -1;
        todo.push({good_edges[cur].size(), cur});
    }
    int ans = 1e9;
    for(int i = 0; i<n; ++i)
        if(find2(i)==i && nxt[i]==-1)
            ans = min(ans, siz[i]);
    for(int i = 0; i<n; ++i){
        int x = find2(i);
        res[i] = (nxt[x]==-1 && siz[x]==ans)?1:0;
    }
    return res;
}

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