Submission #774143

#	Time	Username	Problem	Language	Result	Execution time	Memory
774143		SanguineChameleon	Keys (IOI21_keys)	C++17	9 / 100	810 ms	175052 KiB

keys

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

const int maxN = 3e5 + 20;
deque<int> Q;

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()) {
			Q.push_back(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(comp &X, comp &Y) {
	if (X.rooms.size() > Y.rooms.size()) {
		merge(Y, X);
		return;
	}
	Y.par = -1;
	for (auto u: X.rooms) {
		comp_id[u] = Y.id;
		Y.rooms.insert(u);
	}
	if (X.cands.size() > Y.cands.size()) {
		swap(X.cands, Y.cands);
	}
	for (auto k: X.cands) {
		Y.add_cand(k);
	}
	if (X.keys.size() > Y.keys.size()) {
		swap(X.keys, Y.keys);
	}
	for (auto k: X.cands) {
		Y.add_key(k);
	}
	if (X.edge_cnt > Y.edge_cnt) {
		swap(X.edges, Y.edges);
		swap(X.edge_cnt, Y.edge_cnt);
	}
	for (auto p: X.edges) {
		int k = p.first;
		for (auto e: p.second) {
			int u = e.first;
			int v = e.second;
			Y.add_edge(u, v, k);
		}
	}
}

void expand(int X) {
	if (comps[X].par != -1) {
		return;
	}
	while (!comps[X].cands.empty()) {
		auto it1 = comps[X].cands.begin();
		auto it2 = comps[X].edges.find(*it1);
		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(comps[Y], comps[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 (!Q.empty()) {
		expand(Q.front());
		Q.pop_front();
	}
	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: 0 / 11
• Subtask 3: 0 / 17
• Subtask 4: 0 / 30
• Subtask 5: 0 / 33