Submission #671792

#	Time	Username	Problem	Language	Result	Execution time	Memory
671792		flappybird	Keys (IOI21_keys)	C++17	100 / 100	951 ms	386748 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];
set<pii> 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 mcnt[MAX]; //max move cnt

int merge_two(int u, int v) {
	u = find(u);
	v = find(v);
	if (u == v) return u;
	if (mcnt[u] >= mcnt[v]) swap(u, v);
	mcnt[v] = max(mcnt[v], mcnt[u] + 1);
	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);
		while (1) {
			auto it = mp[v].lower_bound(pii(x, -1));
			if (it == mp[v].end() || it->first != x) break;
			adj[v].emplace(it->second);
			mp[v].erase(it);
		}
	}
	for (auto& [k, nv] : mp[u]) {
		if (exists(keys[v], k)) adj[v].push(nv);
		else mp[v].insert(pii(k, nv));
	}
	while (adj[u].size()) adj[v].push(adj[u].front()), adj[u].pop();
	return v;
}

void merge(int u, int v) {
	u = find(u);
	v = find(v);
	if (u == v) return;
	int loc = v;
	int m = v;
	vector<int> all;
	while (find(loc) != find(u)) {
		loc = find(nxt[loc]);
		all.push_back(loc);
	}
	for (auto x : all) v = merge_two(v, x);
	while (adj[v].size()) {
		int t = adj[v].front();
		if (find(t) != find(v)) {
			nxt[v] = t;
			if (find_cycle(t) == find_cycle(v)) lst.emplace(v, t);
			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);
	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].emplace(C[e], 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)) lst.emplace(i, t);
			else merge_cycle(i, t);
		}
		else {
			mn = 1;
			mlist.push_back(i);
		}
	}
	int iters = 0;
	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;
}

Compilation message (stderr)

keys.cpp: In function 'void merge(int, int)':
keys.cpp:79:6: warning: unused variable 'm' [-Wunused-variable]
   79 |  int m = v;
      |      ^
keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:138:6: warning: unused variable 'iters' [-Wunused-variable]
  138 |  int iters = 0;
      |      ^~~~~

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