Submission #823236

#	Time	Username	Problem	Language	Result	Execution time	Memory
823236		Blagoj	Keys (IOI21_keys)	C++17	100 / 100	560 ms	59148 KiB

keys

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

using namespace std;

#define all(x) x.begin(), x.end()

int ldr[300005];
bool dead[300005];

int Find(int x) {
	if (x != ldr[x]) ldr[x] = Find(ldr[x]);
	return ldr[x]; 
}

void Merge(int x, int y) {
	ldr[Find(x)] = ldr[Find(y)];
}

vector<int> keys(300005), reach, locked[300005], hasLock, mn;
vector<pair<int, int>> g[300005];

int last[300005], ans;
bool visited[300005], has[300005];

void clear() {
	for (auto x : reach) has[keys[x]] = 0;
	for (auto x : hasLock) locked[x].clear();
	reach.clear();
	hasLock.clear();
}

void Bfs(int cur, int it) {
	last[cur] = it;
	queue<int> q;
	q.push(cur);
	while (q.size()) {
		int fr = q.front();
		q.pop();
		if (Find(fr) != cur) {
			Merge(cur, Find(fr));
			last[Find(fr)] = it;
			clear();
			return;
		}
		if (visited[fr]) continue;
		visited[fr] = 1;
		reach.push_back(fr);
		int type = keys[fr];
		if (has[type] == 0) {
			for (auto x : locked[type]) q.push(x);
			locked[type].clear();
			has[type] = 1;
		}
		for (auto x : g[fr]) {
			if (has[x.second]) q.push(x.first);
			else {
				locked[x.second].push_back(x.first);
				hasLock.push_back(x.second);
			}
		}
	}
	dead[cur] = 1;
	if (reach.size() < ans) {
		ans = reach.size();
		mn.clear();
	}
	if (reach.size() == ans) for (auto x : reach) mn.push_back(x);
	clear();
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size(), m = u.size();
	for (int i = 0; i < n; i++) keys[i] = r[i], ldr[i] = i;
	for (int i = 0; i < m; i++) {
		g[u[i]].push_back({v[i], c[i]});
		g[v[i]].push_back({u[i], c[i]});
	}
	ans = n + 1;
	for (int it = 1; ; it++) {
		memset(visited, 0, sizeof(visited));
		bool flag = 0;
		for (int i = 0; i < n; i++) {
			if (Find(i) == i && !dead[i] && last[i] != it) {
				Bfs(i, it);
				flag = 1;
			}
		}
		if (!flag) break;
	}
	vector<int> ret(n);
	for (auto x : mn) ret[x] = 1;
	return ret;
}

Compilation message (stderr)

keys.cpp: In function 'void Bfs(int, int)':
keys.cpp:64:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |  if (reach.size() < ans) {
      |      ~~~~~~~~~~~~~^~~~~
keys.cpp:68:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |  if (reach.size() == ans) for (auto x : reach) mn.push_back(x);
      |      ~~~~~~~~~~~~~^~~~~~

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