oj.uz

Submission #113248

# Submission time Handle Problem Language Result Execution time Memory
113248 2019-05-24T12:07:09 Z tutis Pictionary (COCI18_pictionary) C++17
140 / 140
 264 ms 3400 KB 
/*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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1536 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1784 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 2416 KB Output is correct
2 Correct 123 ms 2356 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 2808 KB Output is correct
2 Correct 190 ms 2680 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 2296 KB Output is correct
2 Correct 96 ms 2336 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 2492 KB Output is correct
2 Correct 119 ms 2396 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 2680 KB Output is correct
2 Correct 100 ms 2384 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 2908 KB Output is correct
2 Correct 178 ms 2968 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 3200 KB Output is correct
2 Correct 192 ms 3064 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 3400 KB Output is correct
2 Correct 264 ms 3356 KB Output is correct