Submission #1043726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043726		42kangaroo	Keys (IOI21_keys)	C++17	37 / 100	3037 ms	91900 KiB

keys

#include "keys.h"
#include "bits/stdc++.h"

using namespace std;

using g_t = vector<map<int, vector<int>>>;
using g_t2 = vector<vector<int>>;

int find(int a, vector<int> &p) {
	if (p[a] == a) return a;
	return p[a] = find(p[a], p);
}

bool unite(int a, int b, vector<int> &p, g_t &g, vector<int> &si, vector<set<int>> &in) {
	a = find(a, p), b = find(b, p);
	if (a == b) return false;
	if (si[a] < si[b]) swap(a, b);
	p[b] = a;
	si[a] += si[b];
	in[a].insert(in[b].begin(), in[b].end());
	for (auto [co, e]: g[b]) {
		for (auto ed: e) {
			if (find(ed, p) != a)
				g[a][co].push_back(ed);
		}
	}
	return true;
}

void poO(int n, int &t, g_t &g, g_t2 &rev, vector<set<int>> &whi, vector<int> &poOv, vector<int> &p) {
	n = find(n, p);
	if (poOv[n] != -1) return;
	poOv[n] = -2;
	for (auto e: whi[n]) {
		if (g[n].find(e) != g[n].end()) {
			for (auto f: g[n][e]) {
				f = find(f, p);
				rev[f].push_back(n);
				poO(f, t, g, rev, whi, poOv, p);
			}
		}
	}
	poOv[n] = t++;
}

void markDfs(int n, int co, g_t2 &g, vector<int>& col, vector<int> &p) {
	n = find(n, p);
	if (col[n] != -1) return;
	col[n] = co;
	for (auto e: g[n]) {
		e = find(e, p);
		markDfs(e, co, g, col, p);
	}
}

std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
	int n = r.size();
	g_t in(r.size());
	for (int i = 0; i < u.size(); ++i) {
		in[u[i]][c[i]].push_back(v[i]);
		in[v[i]][c[i]].push_back(u[i]);
	}
	vector<int> p(n), si(n, 1);
	iota(p.begin(), p.end(), 0);
	vector<set<int>> whi(n);
	for (int i = 0; i < n; ++i) {
		whi[i].insert(r[i]);
	}
	bool ch = true;
	while (ch) {
		ch = false;
		int t = 0;
		vector<int> pos(n, -1);
		g_t2 gT(n);
		for (int i = 0; i < n; ++i) {
			poO(i, t, in, gT, whi, pos, p);
		}
		vector<int> o(n);
		std::iota(o.begin(), o.end(), 0);
		std::sort(o.begin(), o.end(), [&](int l, int r) { return pos[l] > pos[r]; });
		vector<int> col(n, -1);
		for (int i = 0; i < n; ++i) {
			if (pos[o[i]] != -1) {
				markDfs(o[i], o[i], gT, col, p);
			}
		}
		for (int i = 0; i < n; ++i) {
			if (col[i] != -1) ch = unite(col[i], i, p, in, si, whi) || ch;
		}
	}
	vector<int> re(n, 1);
	for (int i = 0; i < n; ++i) {
		if (i == find(i, p)) {
			for (auto e: whi[i]) {
				if (in[i].find(e) != in[i].end()) {
					for (auto f: in[i][e]) {
						f = find(f, p);
						re[i] = re[i] && f == i;
					}
				}
			}
		}
	}
	int mi = n;
	for (int i = 0; i < n; ++i) {
		if (re[find(i, p)]) {
			mi = min(mi, si[find(i, p)]);
		}
	}
	for (int i = 0; i < n; ++i) {
		re[i] = re[find(i, p)] && mi == si[find(i, p)];
	}
	return re;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i < u.size(); ++i) {
      |                  ~~^~~~~~~~~~

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