oj.uz

Submission #83204

# Submission time Handle Problem Language Result Execution time Memory
83204 2018-11-06T02:12:09 Z luciocf Pictionary (COCI18_pictionary) C++14
140 / 140
 288 ms 2912 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int pai[maxn], sz[maxn], edge[maxn], nivel[maxn];

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

void Join(int x, int y, int tt)
{
	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, edge[y] = tt;
}

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

int dfs(int u)
{
	if (u == Find(1)) return 0;
	return nivel[u] = dfs(pai[u])+1;
}

int lca(int u, int v)
{
	int ans = -1;
	while (u != v)
	{
		if (nivel[u] > nivel[v]) ans = max(ans, edge[u]), u = pai[u];
		else ans = max(ans, edge[v]), v = pai[v];
	}

	return ans;
}

int main(void)
{
	int n, m, q;
	cin >> n >> m >> q;

	init(n);

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

	for (int i = 1; i <= n; i++)
		dfs(i);

	for (int i = 1; i <= q; i++)
	{
		int u, v;
		cin >> u >> v;

		cout << lca(u, v) << "\n";	
	}
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 508 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 812 KB Output is correct
2 Correct 161 ms 812 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 812 KB Output is correct
2 Correct 198 ms 884 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 1044 KB Output is correct
2 Correct 137 ms 1048 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 1336 KB Output is correct
2 Correct 134 ms 1336 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 1824 KB Output is correct
2 Correct 126 ms 1824 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 1952 KB Output is correct
2 Correct 225 ms 2160 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 2400 KB Output is correct
2 Correct 262 ms 2632 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 2912 KB Output is correct
2 Correct 282 ms 2912 KB Output is correct