Submission #523883

#	Time	Username	Problem	Language	Result	Execution time	Memory
523883		prvocislo	Keys (IOI21_keys)	C++17	100 / 100	743 ms	56796 KiB

keys

// podla https://codeforces.com/blog/entry/92083?#comment-807994
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <chrono>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <queue>
#include <bitset>
#include <cmath>
#include <cassert>
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 3e5 + 5;
int par[maxn]; // aspon jeden z korenov tohto union-findu dava optimalnu odpoved.
int root(int u)
{
	return par[u] == u ? u : par[u] = root(par[u]);
}
void merge(int p, int v)
{
	par[root(v)] = root(p);
}
int ans = maxn; // minimalna dosiahnutelnost
vector<int> val; // hodnoty, ktore nadobudaju toto minimum
int mykey[maxn]; // moj kluc
vector<pair<int, int> > g[maxn]; // hrany
vector<int> locked[maxn]; // tie vrcholy, ku ktorym sa zatial neviem dostat
bool keys[maxn]; // keys[i] = mame kluc i?
int last[maxn]; // last[i] = posledna iteracia v ktorej sme navstivili ten vrchol i
bool out[maxn]; // out[i] = je i vrchol, z ktoreho sa uz nevieme dostat prec?
bool vis[maxn]; // vis[i] = navstiveny?
vector<int> reach; // kam sa vieme dostat?
void clear() // upraceme po bfsku
{
	for (int i : reach)
	{
		keys[mykey[i]] = 0;
		for (pair<int, int> j : g[i]) locked[j.second].clear();
	}
	reach.clear();
}
void find_better(int u, int round)
{
	queue<int> q;
	q.push(u);
	while (q.size())
	{
		int v = q.front();
		q.pop();
		if (root(v) != u) // nasli sme vrchol, ktory je aspon taky dobry ako u
		{
			merge(v, u);
			last[root(v)] = round;
			clear();
			return;
		}
		if (vis[v]) continue;
		vis[v] = true;
		reach.push_back(v);
		if (!keys[mykey[v]]) // dostali sme novy kluc
		{
			keys[mykey[v]] = true;
			for (int i : locked[mykey[v]]) q.push(i); // odomkli sa nam nove vrcholy
			locked[mykey[v]].clear();
		}
		for (pair<int, int> i : g[v]) // ideme popozerat hrany odtialto a rozsirit sa
		{
			if (keys[i.second]) q.push(i.first); // mame spravny kluc
			else locked[i.second].push_back(i.first); // nemame spravny kluc
		}
	}
	out[u] = true; // nevieme uz nikde inde ist, takze u je jeden z kandidatov na odpoved
	if (reach.size() < ans) ans = reach.size(), val.clear();
	if (reach.size() == ans) for (int i : reach) val.push_back(i);
	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++) mykey[i] = r[i], par[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] });
	for (int round = 1; ; round++)
	{
		fill(vis, vis + maxn, false);
		bool change = false;
		for (int i = 0; i < n; i++) if (i == par[i] && !out[i] && last[i] != round)
			find_better(i, round), change = true;
		if (!change) break;
	}
	vector<int> ans(n, 0);
	for (int i : val) ans[i] = 1;
	return ans;
}

Compilation message (stderr)

keys.cpp: In function 'void find_better(int, int)':
keys.cpp:80:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |  if (reach.size() < ans) ans = reach.size(), val.clear();
      |      ~~~~~~~~~~~~~^~~~~
keys.cpp:81:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   81 |  if (reach.size() == ans) for (int i : reach) val.push_back(i);
      |      ~~~~~~~~~~~~~^~~~~~

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