Submission #749106

#	Time	Username	Problem	Language	Result	Execution time	Memory
749106		numberes	Keys (IOI21_keys)	C++17	100 / 100	722 ms	69120 KiB

keys

/**
 * @date    2023-05-27 16:46:26
 * RAmen!
 */
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define ll long long
using namespace std;
int n, key[300005], spe[300005], iss[300005], fa[300005];
vector<int> comp[300005];
int head[300005], nxt[600005], tot;
pii to[600005];
vector<int> col[300005];
bool vis[300005], visc[300005];
vector<int> cl, clc;
int ans; vector<int> out;
int fnd(int x) {
	return x == fa[x] ? x : fa[x] = fnd(fa[x]);
}
void add_edge(int u, int v, int w) {
	nxt[++tot] = head[u]; head[u] = tot; to[tot] = mp(v, w);
}
void clean() {
	for(auto u : cl) vis[u] = 0;
	for(auto x : clc) {col[x].clear(); visc[x] = 0;} clc.clear();
}
pii bfs(int s) {
	queue<int> q; q.push(s); int num = 1;
	cl.pb(s); clc.pb(key[s]); vis[s] = 1;
	while(!q.empty()) {
		int u = q.front(); q.pop();
		if(fnd(u) != fnd(s)) {
			clean(); return mp(fnd(u), num);
		}
		for(auto v : col[key[u]]) if(!vis[v]) {
			vis[v] = 1; num++; cl.pb(v); q.push(v);
		}
		col[key[u]].clear(); visc[key[u]] = 1; clc.pb(key[u]);
		pii now = to[head[u]];
		for(int i = head[u]; i; i = nxt[i], now = to[i]) if(!vis[now.fi]) {
			if(visc[now.se]) {
				vis[now.fi] = 1; num++; cl.pb(now.fi); q.push(now.fi);
			}
			else {
				clc.pb(now.se); col[now.se].pb(now.fi);
			}
		}
	}
	clean(); return mp(-1, num);
}
void merge(int a, int b) {
	if(b == -1 || spe[b] == -1) {
		iss[spe[a]] = 0; spe[a] = -1;
		return;
	}
	if(comp[a].size() > comp[b].size()) {
		comp[a].insert(comp[a].end(), comp[b].begin(), comp[b].end());
		comp[b].clear();
		iss[spe[a]] = 0; spe[a] = spe[b]; fa[b] = a;
	}
	else {
		comp[b].insert(comp[b].end(), comp[a].begin(), comp[a].end());
		comp[a].clear();
		iss[spe[a]] = 0; fa[a] = b;
	}
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	for(auto x : r) key[++n] = x + 1;
	for(int i = 0; i < (int)u.size(); i++) {
		u[i]++; v[i]++; c[i]++;
		add_edge(u[i], v[i], c[i]); add_edge(v[i], u[i], c[i]);
	}
	/*int m; cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> key[i]; key[i]++;
	}
	for(int i = 1; i <= m; i++) {
		int u, v, c; cin >> u >> v >> c;
		u++; v++; c++;
		add_edge(u, v, c); add_edge(v, u, c);
	}*/
	for(int i = 1; i <= n; i++) {
		fa[i] = i; iss[i] = 1; spe[i] = i; comp[i].pb(i);
	}
	ans = 1e9;
	for(int t = 0; t < 25; t++) {
		for(int i = 1; i <= n; i++) if(iss[i]) {
			pii res = bfs(i);
			if(res.fi == -1) {
				if(ans > res.se) {
					ans = res.se; out = cl;
				}
				else if(ans == res.se)
					out.insert(out.end(), cl.begin(), cl.end());
			}
			cl.clear();
			merge(fnd(i), res.fi);
		}
	}
	vector<int> ret;
	for(int i = 1; i <= n; i++)
		ret.pb(0);
	for(auto x : out) {
		// cout << x << endl;
		ret[x - 1] = 1;
	}
	return ret;
}

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