Submission #1210658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210658		garam1732	Keys (IOI21_keys)	C++20	9 / 100	285 ms	107044 KiB

keys

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*3;
const ll MOD = 998244353;
const ll INF = 1e16;

vector<pi> adj[MAXN];
int nx[MAXN], idx[MAXN];
//vector<int> pv[MAXN];

set<int> col[MAXN];
set<pi> edge[MAXN];
int cnt[MAXN];

vector<int> cnct, pnt; 
int root(int x, vector<int>& par) { return par[x]==x?x:par[x]=root(par[x], par); }
void merge(int x, int y, vector<int>& par) {
    x = root(x, par), y = root(y, par);
    if(x^y) par[y] = x;
}

void merge_stl(int a, int b, bool flag) {
    merge(a, b, pnt);

    if(flag) {
        nx[a] = -1;
        vector<pi> tmp;
        for(int c : col[b]) {
            while(nx[a]==-1) {
                auto it = edge[a].lower_bound(pi(c,0));
                if(it == edge[a].end() || it->ff != c) break;
                
                int x = it->ss;
                if(root(x, pnt)==a || root(x, pnt)==b) {
                    edge[a].erase(it); continue;
                }

                nx[a] = x;
            }
        } for(auto [c,x] : edge[b]) { if(nx[a]!=-1) break;
            if(root(x,pnt)==a || root(x,pnt)==b) {
                tmp.push_back(pi(c,x)); continue;
            }

            if(col[a].find(c)!=col[a].end()) {
                nx[a] = x; break;
            }
        } for(auto x:tmp) edge[b].erase(x);
    }

    cnt[a] += cnt[b];
    for(int x : col[b]) {
        col[a].insert(x);
    } for(auto x : edge[b]) {
        edge[a].insert(x);
    } col[b].clear(); edge[b].clear();
}

queue<vector<int> > cycle;
vector<pi> cand;
vector<int> ans;

int vst[MAXN]; // -1: already vst, 0: not vst, 1: current vst
vector<int> track;
void dfs(int here) {
    vst[here] = 1;
    track.push_back(here);

    int there = nx[here];
    if(there == -1) return;
    if(vst[there] == -1) return;
    if(vst[there] == 1) {
        vector<int> v;
        int i=0; while(track[i]^there) i++;
        for(; i<track.size(); i++) v.push_back(track[i]);
        cycle.push(v); return;
    } dfs(there);
}

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();
    for(int i=0; i<m; i++) {
        adj[u[i]].push_back(pi(v[i], c[i]));
        adj[v[i]].push_back(pi(u[i], c[i]));
    } for(int i=0; i<n; i++) {
        col[i].insert(r[i]);
        cnt[i] = 1;

        for(auto [j,w] : adj[i]) {
            edge[i].insert(pi(w, j));
        }
    }

    cnct.resize(n); pnt.resize(n); ans.resize(n);
    for(int i=0; i<n; i++) cnct[i] = pnt[i] = i;

    // nx init
    bool chk = 0;
    memset(nx, -1, sizeof nx);
    for(int i=0; i<n; i++) {
        for(int &j = idx[i]; j<adj[i].size(); j++) {
            int x = adj[i][j].ff, w = adj[i][j].ss;
            if(w == r[i]) {
                nx[i] = x; //pv[x].push_back(i);
                merge(i, nx[i], cnct); break;
            }
        } if(nx[i] == -1) {
            chk=1; ans[i]=1;
        }
    } if(chk) return ans;

    // find cycle
    for(int i=0; i<n; i++) {
        if(!vst[i]) {
            track.clear();
            dfs(i);
            for(int x:track) vst[x]=-1;
        }
    }

    while(cycle.size()) {
        // union cycle, update new nx
        vector<int> v = cycle.front(); cycle.pop();
        for(int i=1; i<v.size(); i++) {
            if(col[v[0]].size()+edge[v[0]].size() < col[v[i]].size()+edge[v[i]].size()) swap(v[0], v[i]);
            merge_stl(v[0], v[i], i+1==v.size());
        }

        if(nx[v[0]] == -1) {
            cand.push_back(pi(cnt[v[0]], v[0]));
            continue;
        }

        // update new cycle
        vector<int> tmp;
        vector<int> new_cycle;
        int x = root(v[0], cnct), y = root(nx[v[0]], cnct);
        if(x == y) {
            new_cycle.push_back(v[0]);
            for(int here = root(nx[v[0]], pnt); here != v[0]; here=root(nx[here], pnt))
                new_cycle.push_back(here);
        } else {
            merge(x, y, cnct);
        }

        // push new cycle
        if(new_cycle.size() > 1) cycle.push(new_cycle);
    }
    
    // return smallest root
    sort(all(cand)); int mn = cand[0].ff;
    for(auto x:cand) { assert(pnt[x.ss]==x.ss);
        if(x.ff==mn) ans[x.ss]=1;
    } for(int i=0; i<n; i++) {
        ans[i] = ans[root(i, pnt)];
    }

	return ans;
}

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