Submission #113248

#	Time	Username	Problem	Language	Result	Execution time	Memory
113248		tutis	Pictionary (COCI18_pictionary)	C++17	140 / 140	264 ms	3400 KiB

pictionary

/*input
9999 2222 2
1025 2405
3154 8949
*/
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct dsu
{
	int pa[101010];
	int sz[101010];
	int time[101010];
	dsu()
	{
		iota(pa, pa + 101010, 0);
		fill_n(sz, 101010, 1);
		fill_n(time, 101010, 101010);
	}
	int root(int i)
	{
		while (pa[i] != i)
			i = pa[i];
		return i;
	}
	bool same(int x, int y)
	{
		return root(x) == root(y);
	}
	void merge(int x, int y, int t)
	{
		x = root(x);
		y = root(y);
		if (x != y)
		{
			if (sz[x] > sz[y])
				swap(x, y);
			pa[x] = y;
			time[x] = t;
			sz[y] += sz[x];
		}
	}
};
int main()
{
	ios_base::sync_with_stdio(false);
	int N, M, Q;
	cin >> N >> M >> Q;
	dsu A;
	for (int x = M; x >= 1; x--)
	{
		for (int a = 2 * x; a <= N; a += x)
		{
			A.merge(a, a - x, M - x + 1);
		}
	}
	while (Q--)
	{
		int a, b;
		cin >> a >> b;
		vector<pair<int, int>>xx;
		vector<pair<int, int>>yy;
		int time = 0;
		while (true)
		{
			xx.push_back({a, time});
			if (A.pa[a] != a)
			{
				time = max(time, A.time[a]);
				a = A.pa[a];
			}
			else
				break;
		}
		time = 0;
		while (true)
		{
			yy.push_back({b, time});
			if (A.pa[b] != b)
			{
				time = max(time, A.time[b]);
				b = A.pa[b];
			}
			else
				break;
		}
		int ans = 101010;
		for (pair<int, int>i : xx)
		{
			for (pair<int, int>j : yy)
			{
				if (i.first == j.first)
					ans = min(ans, max(i.second, j.second));
			}
		}
		cout << ans << "\n";
	}
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14