Submission #671736

#	Time	Username	Problem	Language	Result	Execution time	Memory
671736		flappybird	Keys (IOI21_keys)	C++17	0 / 100	294 ms	497372 KiB

keys

#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef pair<int, int> pii;

#define MAX 301010

int N, M;

int cycle_chk[MAX];

int find_cycle(int v) {
	if (cycle_chk[v] == v) return v;
	else return cycle_chk[v] = find_cycle(cycle_chk[v]);
}

void merge_cycle(int u, int v) {
	u = find_cycle(u);
	v = find_cycle(v);
	cycle_chk[u] = v;
}

int p[MAX];
int num[MAX];
set<int> keys[MAX];
queue<int> adj[MAX];
map<int, vector<int>> mp[MAX];
int nxt[MAX];
vector<int> subv[MAX];

#define exists(st, v) (st.find(v) != st.end())

int find(int v) {
	if (p[v] == v) return v;
	return p[v] = find(p[v]);
}

queue<pii> lst;
int mn;
vector<int> mlist;

int pp[MAX];
int find_last(int v) {
	if (pp[v] == v) return v;
	return pp[v] = find(pp[v]);
}

void merge_last(int u, int v) {
	u = find_last(u);
	v = find_last(v);
	pp[u] = v;
}

void add_lst(int u, int v) {
	if (find_last(u) == find_last(v)) return;
	merge_last(u, v);
	lst.emplace(u, v);
}

void merge(int u, int v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	if (keys[u].size() > keys[v].size()) swap(u, v);
	p[u] = v;
	if (subv[u].size() > subv[v].size()) swap(subv[u], subv[v]);
	for (auto x : subv[u]) subv[v].push_back(x);
	num[v] += num[u];
	for (auto x : keys[u]) {
		keys[v].insert(x);
		if (exists(mp[v], x)) {
			for (auto nxt : mp[v][x]) adj[v].push(find(nxt));
			mp[v].erase(x);
		}
	}
	for (auto& [x, vec] : mp[u]) {
		if (exists(keys[v], x)) for (auto nxt : vec) adj[v].push(find(nxt));
		else for (auto nxt : vec) mp[v][x].push_back(find(nxt));
	}
	while (adj[u].size()) adj[v].push(adj[u].front()), adj[u].pop();
	while (adj[v].size()) {
		int t = adj[v].front();
		if (find(t) != find(v)) {
			nxt[v] = t;
			if (find_cycle(t) == find_cycle(v)) {
				int debug_iters = 0;
				int loc = t;
				int pv = t;
				while (find(loc) != find(v)) {
					debug_iters++;
					assert(debug_iters < 400000);
					loc = nxt[loc];
					loc = find(loc);
					add_lst(loc, pv);
					pv = loc;
				}
			}
			else merge_cycle(t, v);
			break;
		}
		else adj[v].pop();
	}
	if (adj[v].empty()) {
		if (mn > num[v]) {
			mlist = subv[v];
			mn = num[v];
		}
		else if (mn == num[v]) mlist.insert(mlist.end(), subv[v].begin(), subv[v].end());
	}
}

vector<int> radj[MAX];

std::vector<int> find_reachable(std::vector<int> R, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
	N = R.size();
	M = U.size();
	int i;
	for (i = 0; i < N; i++) p[i] = i, num[i] = 1, cycle_chk[i] = i, keys[i].emplace(R[i]), subv[i].push_back(i), pp[i] = i;
	mn = N;
	for (i = 0; i < M; i++) radj[U[i]].push_back(i), radj[V[i]].push_back(i);
	auto to = [&](int v, int e) {
		return U[e] + V[e] - v;
	};
	for (i = 0; i < N; i++) {
		for (auto e : radj[i]) {
			if (C[e] == R[i]) adj[i].emplace(to(i, e));
			else mp[i][C[e]].push_back(to(i, e));
		}
	}
	for (i = 0; i < N; i++) {
		nxt[i] = -1;
		if (adj[i].size()) nxt[i] = adj[i].front();
	}
	for (i = 0; i < N; i++) {
		if (~nxt[i]) {
			int t = nxt[i];
			if (find_cycle(t) == find_cycle(i)) {
				int loc = t;
				int pv = t;
				while (find(loc) != find(i)) {
					loc = nxt[loc];
					loc = find(loc);
					add_lst(loc, pv);
					pv = loc;
				}
			}
			else merge_cycle(i, t);
		}
		else {
			mn = 1;
			mlist.push_back(i);
		}
	}
	while (lst.size()) {
		int u, v;
		tie(u, v) = lst.front();
		lst.pop();
		merge(u, v);
	}
	vector<int> ansv(N);
	for (auto p : mlist) ansv[p] = 1;
	return ansv;
}

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