Submission #776437

#	Time	Username	Problem	Language	Result	Execution time	Memory
776437		GusterGoose27	Keys (IOI21_keys)	C++17	100 / 100	1262 ms	139904 KiB

keys

#include <vector>

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 3e5;
map<int, vector<int>>* all_edges[MAXN];
vector<int> edges[MAXN];
int pos[MAXN];
set<int>* colors[MAXN];
int vis[MAXN];
bool dead[MAXN];
int uf[MAXN];
int edgecount[MAXN];
int sz[MAXN];
int n, m;

int find(int i) {
	return uf[i] == i ? i : uf[i] = find(uf[i]);
}

vector<int> stck;

void make_edges(int i, vector<int> &e) {
	for (int v: e) edges[i].push_back(v);
}

vector<int> &get(map<int, vector<int>> *mp, int v) {
	if (mp->find(v) == mp->end()) {
		vector<int> nv;
		mp->insert(pair<int, vector<int>>(v, nv));
	}
	return mp->at(v);
}

void merge(int i, int j) {
	i = find(i);
	j = find(j);
	assert(i != j);
	if (i == j) return;
	if (edgecount[j] > edgecount[i]) swap(i, j);
	edgecount[i] += edgecount[j];
	uf[j] = i;
	sz[i] += sz[j];
	for (auto it: *all_edges[j]) {
		if (colors[i]->find(it.first) != colors[i]->end()) make_edges(i, it.second);
		else for (int val: it.second) get(all_edges[i], it.first).push_back(val);
	}
	all_edges[j]->clear();
	for (int v: edges[j]) edges[i].push_back(v);
	edges[j].clear();
	for (int c: *colors[j]) {
		make_edges(i, get(all_edges[i], c));
		all_edges[i]->erase(c);
		colors[i]->insert(c);
	}
	colors[j]->clear();
}

void dfs(int cur) {
	vis[cur] = 1;
	stck.push_back(cur);
	bool f = 0;
	for (; pos[cur] < edges[cur].size(); pos[cur]++) {
		int nxt = find(edges[cur][pos[cur]]);
		if (vis[nxt] == 2) {
			stck.pop_back();
			dead[cur] = 1;
			// assert(false);
			f = 1;
			break;
		}
		if (nxt == cur) continue;
		if (vis[nxt] == 1) {
			while (stck.back() != nxt) {
				merge(nxt, stck.back());
				stck.pop_back();
			}
			stck.pop_back();
			nxt = find(nxt);
			dfs(nxt);
			f = 1;
			break;
		}
		else {
			dfs(nxt);
			f = 1;
			if (!stck.empty() && stck.back() == cur) {
				// assert(false);
				dead[cur] = 1;
				stck.pop_back();
			}
			break;
		}
	}
	vis[cur] = 2;
	if (!f) {
		stck.pop_back();
		return;
	}
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	n = r.size();
	m = u.size();
	for (int i = 0; i < n; i++) {
		colors[i] = new set<int>();
		colors[i]->insert(r[i]);
		all_edges[i] = new map<int, vector<int>>();
	}
	for (int i = 0; i < m; i++) {
		if (r[u[i]] == c[i]) edges[u[i]].push_back(v[i]);
		else get(all_edges[u[i]], c[i]).push_back(v[i]);
		swap(u[i], v[i]);
		if (r[u[i]] == c[i]) edges[u[i]].push_back(v[i]);
		else get(all_edges[u[i]], c[i]).push_back(v[i]);
		edgecount[u[i]]++;
		edgecount[v[i]]++;
	}
	iota(uf, uf+n, 0);
	fill(sz, sz+n, 1);
	for (int i = 0; i < n; i++) if (vis[i] == 0) dfs(i);
	vector<int> ans;
	int small = n;
	for (int i = 0; i < n; i++) {
		if (dead[find(i)] || sz[find(i)] > small) continue;
		if (sz[find(i)] < small) {
			small = sz[find(i)];
			ans.clear();
		}
		if (sz[find(i)] == small) ans.push_back(i);
	}
	vector<int> res(n, 0);
	for (int v: ans) res[v] = 1;
	return res;
}

Compilation message (stderr)

keys.cpp: In function 'void dfs(int)':
keys.cpp:67:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for (; pos[cur] < edges[cur].size(); pos[cur]++) {
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~~~

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