oj.uz

Submission #83190

# Submission time Handle Problem Language Result Execution time Memory
83190 2018-11-06T00:02:50 Z luciocf Pictionary (COCI18_pictionary) C++14
56 / 140
 479 ms 8908 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3+10;

int pai[maxn], sz[maxn];

int ans[maxn][maxn];

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

void Join(int x, int y)
{
	x = Find(x), y = Find(y);
	if (x == y) return;

	if (sz[x] < sz[y]) swap(x, y);

	sz[x] += sz[y];
	pai[y] = x;
}

void init(int n)
{
	for (int i = 1; i <= n; i++)
		pai[i] = i, sz[i] = 1;
}

int main(void)
{
	memset(ans, -1, sizeof ans);

	int n, m, q;
	cin >> n >> m >> q;

	init(n);

	vector< pair<int, int> > Q;
	for (int i = 1; i <= q; i++)
	{
		int a, b;
		cin >> a >> b;

		Q.push_back({a, b});
	}

	for (int i = m; i >= 1; i--)
	{
		for (int j = i; j <= n; j += i) 
			Join(j, i);

		for (auto P: Q)
		{
			int a = P.first, b = P.second;
			
			if (Find(a) == Find(b) && ans[a][b] == -1) 
				ans[a][b] = m-i+1;
		}
	}

	for (auto P: Q)
		cout << ans[P.first][P.second] << "\n";
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 4472 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4732 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 5580 KB Output is correct
2 Correct 98 ms 5600 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 5780 KB Output is correct
2 Correct 244 ms 5780 KB Output is correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 8628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 8684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 8820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 8820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 8868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 8908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -