oj.uz

답안 #575543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
575543 2022-06-10T22:10:46 Z Pietra Pictionary (COCI18_pictionary) C++14
140 / 140
 127 ms 29200 KB 
#include<bits/stdc++.h>
using namespace std ; 

const int maxl = 22 ; 
const int maxn = 2e5 + 5 ; 

int n, m, q ;
int  tab[maxl][maxn], mx[maxl][maxn], nivel[maxn] ; 
int sz[maxn], pai[maxn] ; 

vector<pair<int,int>> grafo[maxn] ; 

struct DSU{

	int find(int a){return (pai[a] == a ? a : pai[a] = find(pai[a])) ; }

	void join(int a, int b){
		a = find(a), b = find(b) ; 
		if(sz[a] > sz[b]) swap(a, b) ;
		// tab[0][a] = b ; mx[0][a] = id ;  nivel[a] = nivel[b] + 1 ; 
		sz[b] += sz[a] ; pai[a] = b ; 
	}

} dsu ; 

void dfs(int v, int p){

	tab[0][v] = p ; 

	for(auto a : grafo[v]){
		if(a.first == p || nivel[a.first] != -1) continue ; 
		nivel[a.first] = nivel[v] + 1 ; 
		mx[0][a.first] = a.second ; 
		dfs(a.first, v) ; 
	}

}

int lca(int a, int b){
	
	int ans = 0 ; 

	if(nivel[a] > nivel[b]) swap(a, b) ; 

	for(int i = maxl - 1 ; i >= 0 ; i--){
		if(tab[i][b] != -1 && nivel[tab[i][b]] >= nivel[a]){
			ans = max(ans, mx[i][b]) ;
			b = tab[i][b] ; 
		}
	}

	if(a == b) return ans ; 

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

	return max({ans, mx[0][a], mx[0][b]}) ; 

}

int main(){

	ios_base::sync_with_stdio(false) ; cin.tie(NULL) ; 

	cin >> n >> m >> q ; 

	for(int i = 1 ; i <= n ; i++) pai[i] = i, sz[i] = 1, nivel[i] = -1 ; 

	for(int i = 1 ; i < maxl ; i++){
		for(int j = 1 ; j <= n ; j++){
			tab[i][j] = -1 ; 
		}
	}

	for(int md = m ; md > 0 ; md--){
		for(int id = md + md ; id <= n ; id += md){
			if(dsu.find(md) == dsu.find(id)) continue ; 
			grafo[md].push_back({id, m - md + 1}) ; grafo[id].push_back({md, m - md + 1}) ; 
			dsu.join(md, id) ; 
		}
	}

	nivel[1] = 0 ; 
	dfs(1, 0) ; 

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

	for(int i = 1 ; i <= q ; i++){
		int a, b ; cin >> a >> b ; 
		cout << lca(a, b) << "\n" ; 
	}

}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 5636 KB Output is correct
2 Correct 23 ms 6188 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 5852 KB Output is correct
2 Correct 31 ms 6476 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 10324 KB Output is correct
2 Correct 32 ms 10912 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 12436 KB Output is correct
2 Correct 32 ms 14000 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 15712 KB Output is correct
2 Correct 51 ms 16820 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 19468 KB Output is correct
2 Correct 86 ms 20964 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 22816 KB Output is correct
2 Correct 94 ms 26624 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 27876 KB Output is correct
2 Correct 127 ms 29200 KB Output is correct