Submission #239573

#	Time	Username	Problem	Language	Result	Execution time	Memory
239573		MrRobot_28	Pictionary (COCI18_pictionary)	C++17	140 / 140	218 ms	40540 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector <vector <pair <int, int> > > g;
vector <int> dsu, rang;
int get(int a)
{
	if(a == dsu[a]) return a;
	else return dsu[a] = get(dsu[a]);
}
void unite(int a, int b)
{
	a = get(a);
	b = get(b);
	if(rang[a] < rang[b])
	{
		swap(a, b);
	}
	dsu[b] = a;
	if(rang[a] == rang[b])
	{
		rang[a]++;
	}
}
vector <vector <int> > rmqpr, rmqw;
vector <int> tin, tout;
int timer = 0;
void dfs(int v, int p = -1)
{
	tin[v] = timer++;
	for(int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].first;
		int w = g[v][i].second;
		if(to != p)
		{
			rmqpr[0][to] = v;
			rmqw[0][to] = w;
			dfs(to, v);
		}
	}
	tout[v] = timer++;
}
bool pred(int a, int b)
{
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lcaweight(int a, int b)
{
	if(a == b)
	{
		return 0;
	}
	int ans = 0;
	for(int j = rmqpr.size() - 1; j >= 0; j--)
	{
		if(!pred(rmqpr[j][a], b))
		{
			ans = max(ans, rmqw[j][a]);
			a = rmqpr[j][a];
		}
	}
	for(int j = rmqpr.size() - 1; j >= 0; j--)
	{
		if(!pred(rmqpr[j][b], a))
		{
			ans = max(ans, rmqw[j][b]);
			b = rmqpr[j][b];
		}
	}
	if(!pred(a, b))
	{
		ans = max(ans, rmqw[0][a]);
	}
	if(!pred(b, a))
	{
		ans = max(ans, rmqw[0][b]);
	}
	return ans;
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m, q;
	cin >> n >> m >> q;
	g.resize(n);
	tin.resize(n);
	tout.resize(n);
	dsu.resize(n + 1);
	rang.resize(n + 1);
	for(int i = 1; i <= n; i++)
	{
		dsu[i] = i;
		rang[i] = 1;
	}
	for(int i = m; i >= 1; i--)
	{
		int j = i;
		while(j + i <= n)
		{
			if(get(j) != get(j + i))
			{
				unite(j, j + i);
				g[j - 1].push_back({j + i - 1, m - i + 1});
				g[j + i - 1].push_back({j - 1, m - i + 1});
			}
			j += i;
		}
	}
	int t = log2(n) + 1;
	rmqpr.resize(t, vector <int> (n, 0));
	rmqw.resize(t, vector <int> (n, 0));
	dfs(0);
	for(int i = 1; i < t; i++)
	{
		for(int j = 0; j < n; j++)
		{
			rmqpr[i][j] = rmqpr[i - 1][rmqpr[i - 1][j]];
			rmqw[i][j] = max(rmqw[i - 1][j], rmqw[i - 1][rmqpr[i - 1][j]]);
		}
	}
	while(q--)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		cout << lcaweight(a, b) << "\n";
	}
    return 0;
}

Compilation message (stderr)

pictionary.cpp: In function 'void dfs(long long int, long long int)':
pictionary.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[v].size(); i++)
                 ~~^~~~~~~~~~~~~

• 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