oj.uz

답안 #239573

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
239573 2020-06-16T12:27:48 Z MrRobot_28 Pictionary (COCI18_pictionary) C++17
140 / 140
 218 ms 40540 KB 
#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

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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 512 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 640 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 1408 KB Output is correct
2 Correct 32 ms 1400 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 1912 KB Output is correct
2 Correct 38 ms 1760 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 9032 KB Output is correct
2 Correct 42 ms 8912 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 12288 KB Output is correct
2 Correct 75 ms 14264 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 18296 KB Output is correct
2 Correct 81 ms 19064 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 24340 KB Output is correct
2 Correct 147 ms 28236 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 31604 KB Output is correct
2 Correct 182 ms 35872 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 218 ms 40540 KB Output is correct
2 Correct 204 ms 40348 KB Output is correct