oj.uz

Submission #83442

# Submission time Handle Problem Language Result Execution time Memory
83442 2018-11-07T16:35:52 Z luciocf Pictionary (COCI18_pictionary) C++14
140 / 140
 106 ms 27796 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

const int maxl = 15;

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

int tab[2][maxn][maxl], n;

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;
}

void build(void)
{
	memset(tab, -1, sizeof tab);

	for (int i = 1; i <= n; i++)
		tab[0][i][0] = pai[i], tab[1][i][0] = edge[i];

	for (int j = 1; j < maxl; j++)
		for (int i = 1; i <= n; i++)
			if (tab[0][i][j-1] != -1)
				tab[0][i][j] = tab[0][tab[0][i][j-1]][j-1], tab[1][i][j] = max(tab[1][i][j-1], tab[1][tab[0][i][j-1]][j-1]);
}

int lca(int u, int v)
{
	int ans = -1;

	if (nivel[u] < nivel[v]) swap(u, v);

	for (int i = maxl-1; i >= 0; i--)
		if (nivel[u]-(1<<i) >= nivel[v])
			ans = max(ans, tab[1][u][i]), u = tab[0][u][i];

	if (u == v) return ans;

	for (int i = maxl-1; i >= 0; i--)
		if (tab[0][u][i] != -1 && tab[0][v][i] != -1 & tab[0][u][i] != tab[0][v][i])
			ans = max({ans, tab[1][u][i], tab[1][v][i]}), u = tab[0][u][i], v = tab[0][v][i];

	return max({ans, edge[u], edge[v]});
}

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);

	int 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);

	build();

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

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

Compilation message

pictionary.cpp: In function 'int lca(int, int)':
pictionary.cpp:67:42: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   if (tab[0][u][i] != -1 && tab[0][v][i] != -1 & tab[0][u][i] != tab[0][v][i])
                             ~~~~~~~~~~~~~^~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12152 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 12460 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13188 KB Output is correct
2 Correct 36 ms 13936 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14932 KB Output is correct
2 Correct 42 ms 15684 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 16348 KB Output is correct
2 Correct 38 ms 16868 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 17644 KB Output is correct
2 Correct 43 ms 18224 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 19448 KB Output is correct
2 Correct 49 ms 19968 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 21280 KB Output is correct
2 Correct 82 ms 22636 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 23884 KB Output is correct
2 Correct 91 ms 25112 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 26604 KB Output is correct
2 Correct 103 ms 27796 KB Output is correct