Submission #774311

#	Time	Username	Problem	Language	Result	Execution time	Memory
774311		SanguineChameleon	Keys (IOI21_keys)	C++17	100 / 100	2355 ms	327156 KiB

keys

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

const int maxN = 3e5 + 20;
set<int> S;

struct comp {
	set<int> rooms;
	map<int, set<pair<int, int>>> edges;
	set<int> cands, keys;
	int edge_cnt = 0;
	int id = -1;
	int par = -1;

	void add_cand(int k) {
		if (par == -1 && cands.empty()) {
			S.insert(id);
		}
		cands.insert(k);
	}

	void add_key(int k) {
		keys.insert(k);
		if (edges.find(k) != edges.end()) {
			add_cand(k);
		}
	}

	void add_edge(int u, int v, int k) {
		if (u > v) {
			swap(u, v);
		}
		if (edges[k].find(make_pair(u, v)) == edges[k].end()) {
			edges[k].emplace(u, v);
			edge_cnt++;
		}
		if (keys.find(k) != keys.end()) {
			add_cand(k);
		}
	}
};

struct DSU {
	int par[maxN];
	int depth[maxN];

	void init(int N) {
		for (int i = 0; i < N; i++) {
			par[i] = -1;
			depth[i] = 0;
		}
	}

	int root(int u) {
		return (par[u] == -1 ? u : (par[u] = root(par[u])));
	}

	void join(int u, int v) {
		u = root(u);
		v = root(v);
		if (depth[u] > depth[v]) {
			swap(u, v);
		}
		par[u] = v;
		if (depth[u] == depth[v]) {
			depth[v]++;
		}
	}
} D;

comp comps[maxN];
int comp_id[maxN];

void merge(int X, int Y) {
	if (comps[X].rooms.size() > comps[Y].rooms.size()) {
		swap(X, Y);
	}
	comps[Y].par = -1;
	for (auto u: comps[X].rooms) {
		comp_id[u] = Y;
		comps[Y].rooms.insert(u);
	}
	if (comps[X].cands.size() > comps[Y].cands.size()) {
		swap(comps[X].cands, comps[Y].cands);
	}
	for (auto k: comps[X].cands) {
		comps[Y].add_cand(k);
	}
	if ((int)comps[X].keys.size() + comps[X].edge_cnt > (int)comps[Y].keys.size() + comps[Y].edge_cnt) {
		swap(comps[X].keys, comps[Y].keys);
		swap(comps[X].edges, comps[Y].edges);
		swap(comps[X].edge_cnt, comps[Y].edge_cnt);
	}
	for (auto k: comps[X].keys) {
		comps[Y].add_key(k);
	}
	for (auto p: comps[X].edges) {
		int k = p.first;
		for (auto e: p.second) {
			int u = e.first;
			int v = e.second;
			comps[Y].add_edge(u, v, k);
		}
	}
}

void expand(int X) {
	if (comps[X].par != -1 || comp_id[X] != X) {
		return;
	}
	while (!comps[X].cands.empty()) {
		auto it1 = comps[X].cands.begin();
		auto it2 = comps[X].edges.find(*it1);
		if (it2 == comps[X].edges.end()) {
			comps[X].cands.erase(it1);
			continue;
		}
		auto it3 = it2->second.begin();
		it2->second.erase(it3);
		if (it2->second.empty()) {
			comps[X].cands.erase(it1);
			comps[X].edges.erase(it2);
		}
		int u = it3->first;
		int v = it3->second;
		if (comps[X].rooms.find(u) == comps[X].rooms.end()) {
			swap(u, v);
		}
		if (D.root(u) != D.root(v)) {
			D.join(u, v);
			comps[X].par = comp_id[v];
			return;
		}
		v = comp_id[v];
		vector<int> path;
		while (v != X) {
			path.push_back(v);
			v = comp_id[comps[v].par];
		}
		for (auto Y: path) {
			merge(Y, X);
			X = comp_id[X];
		}
	}
}

vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
	int N = R.size();
	int M = U.size();
	D.init(N);
	for (int i = 0; i < N; i++) {
		comps[i].id = i;
		comps[i].rooms.insert(i);
		comp_id[i] = i;
		comps[i].add_key(R[i]);
	}
	for (int i = 0; i < M; i++) {
		comps[U[i]].add_edge(U[i], V[i], C[i]);
		comps[V[i]].add_edge(U[i], V[i], C[i]);
	}
	while (!S.empty()) {
		int X = *S.begin();
		S.erase(S.begin());
		expand(X);
	}
	int mi = N + 1;
	for (int i = 0; i < N; i++) {
		if (comps[comp_id[i]].par == -1) {
			mi = min(mi, (int)comps[comp_id[i]].rooms.size());
		}
	}
	vector<int> res(N);
	for (int i = 0; i < N; i++) {
		res[i] = (comps[comp_id[i]].par == -1 && (int)comps[comp_id[i]].rooms.size() == mi);
	}
	return res;
}

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