Submission #1053176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053176		aykhn	Keys (IOI21_keys)	C++17	100 / 100	1230 ms	82108 KiB

keys

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

using namespace std;

const int MXN = 3e5 + 5;

struct DSU
{
	vector<int> e, lab;
	void init(int n)
	{
		e.assign(n, -1);
		lab.resize(n);
		iota(lab.begin(), lab.end(), 0);
	}
	int get(int x)
	{
		if (e[x] < 0) return x;
		return e[x] = get(e[x]);
	}
	int getlab(int x)
	{
		return lab[get(x)];
	}
	void unite(int x, int y)
	{
		// y -> x
		x = get(x), y = get(y);
		if (x == y) return;
		if (e[x] < e[y])
		{
			e[x] += e[y];
			e[y] = x;
		}
		else
		{
			lab[y] = lab[x];
			e[y] += e[x];
			e[x] = y;
		}
	}
};

int n;
vector<array<int, 2>> adj[MXN];
vector<int> r, c;
queue<int> q;
map<int, vector<int>> mp;
set<int> keys;
DSU dsu;
int found[MXN];
int ans[MXN];
int used[MXN];

vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> C)
{
	n = R.size(), r = R, c = C;
	dsu.init(n);
	for (int i = 0; i < u.size(); i++)
	{
		adj[u[i]].push_back({v[i], c[i]});
		adj[v[i]].push_back({u[i], c[i]});
	}
	fill(found, found + MXN, 1);
	while (1)
	{
		vector<array<int, 2>> vv;
		vector<int> alive, cc;
		for (int i = 0; i < n; i++)
		{
			if (dsu.getlab(i) == i && found[i]) alive.push_back(i); 
		}
		for (int &i : alive)
		{
			// cout << "! " << i << ' ';
			while (!q.empty()) q.pop();
			mp.clear(), keys.clear();
			found[i] = 0;
			used[i] = 1;
			cc = {i};
			q.push(i);
			// cout << i << ": ";
			while (!q.empty())
			{
				int x = q.front();
				q.pop();
				// cout << x << ' ';
				if (dsu.getlab(x) != i)
				{
					found[i] = 1;
					vv.push_back({dsu.get(i), dsu.get(x)});
					break;
				}
				if (mp.find(r[x]) != mp.end())
				{
					vector<int> &v = mp[r[x]];
					while (!v.empty())
					{
						if (!used[v.back()])
						{
							used[v.back()] = 1;
							cc.push_back(v.back());
							q.push(v.back());
						}
						v.pop_back();
					}
				}
				keys.insert(r[x]);
				for (array<int, 2> &v : adj[x])
				{
					// cout << v[0] << ' ' << v[1] << ", ";
					if (used[v[0]]) continue;
					if (keys.find(v[1]) == keys.end()) mp[v[1]].push_back(v[0]);
					else 
					{
						used[v[0]] = 1;
						cc.push_back(v[0]);
						q.push(v[0]);
					}
				}
				// cout << " | ";
			}
			// cout << '\n';
			for (int &i : cc) used[i] = 0;
		}
		for (array<int, 2> &i : vv) 
		{
			dsu.unite(i[1], i[0]);
			// cout << i[0] << " -> " << i[1] << '\n';
		}
		if (vv.empty()) break;
	}
	int mn = n * 100;
	for (int i = 0; i < n; i++)
	{
		if (dsu.getlab(i) != i) continue;
		while (!q.empty()) q.pop();
		vector<int> cc;
		mp.clear(), keys.clear();
		used[i] = 1;
		cc = {i};
		q.push(i);
		while (!q.empty())
		{
			int x = q.front();
			q.pop();
			if (mp.find(r[x]) != mp.end())
			{
				vector<int> &v = mp[r[x]];
				while (!v.empty())
				{
					if (!used[v.back()])
					{
						used[v.back()] = 1;
						cc.push_back(v.back());
						q.push(v.back());
					}
					v.pop_back();
				}
			}
			keys.insert(r[x]);
			for (array<int, 2> &v : adj[x])
			{
				if (used[v[0]]) continue;
				if (keys.find(v[1]) == keys.end()) mp[v[1]].push_back(v[0]);
				else 
				{
					used[v[0]] = 1;
					cc.push_back(v[0]);
					q.push(v[0]);
				}
			}
		}
		for (int &j : cc) 
		{
			ans[j] = cc.size();
		}
		mn = min(mn, ans[cc[0]]);
		for (int &i : cc) used[i] = 0;
	}
	vector<int> res(n, 0);
	for (int i = 0; i < n; i++)
	{
		if (ans[i] == mn) res[i] = 1;
	}
	return res;
}

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:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for (int i = 0; i < u.size(); i++)
      |                  ~~^~~~~~~~~~

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