oj.uz

답안 #719383

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
719383 2023-04-05T21:18:58 Z Doncho_Bonboncho Pictionary (COCI18_pictionary) C++14
140 / 140
 156 ms 33016 KB 
#include <bits/stdc++.h>
#include <functional>
#include <vector>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e5 + 42;
const int INF = 1e9;
const int mod = 1e9 + 7;

int par[MAX_N];
int sz[MAX_N];
int get( int x ){ return par[x] = ( x == par[x] ? x : get(par[x]) ); }
void uni( int a, int b ){
	a = get(a);
	b = get(b);
	if( a == b ) return;
	if( sz[a] > sz[b] ){
		par[b] = a;
		sz[a] += sz[b];
	}else{
		par[a] = b;
		sz[b] += sz[a];	
	}
}

std::vector<std::pair<int, int>> v[MAX_N];
int lca[MAX_N][30];
int maxLca[MAX_N][30];
bool viz[MAX_N];
int dep[MAX_N];
void dfs( int x ){
	viz[x] = true;
	for( auto j : v[x] ){
		if( !viz[j.first] ){
			dep[j.first] = dep[x] + 1;
			lca[j.first][0] = x;
			maxLca[j.first][0] = j.second;
			dfs( j.first );
		}
	}
}

ll st;
int getLca( int a, int b ){
	if( dep[a] > dep[b] ) std::swap( a, b );
	int diff = dep[b] - dep[a];
	for( int i = st-1 ; i>=0 ; i-- ){
		if( (1<<i)&diff ){
			b = lca[b][i];
		}
	}
	if( a == b ) return a;
	for( int i=st-1 ; i>=0 ; i-- ){
		if( lca[a][i] != lca[b][i] ){
			a = lca[a][i];
			b = lca[b][i];
		}
	}

	return lca[a][0];
}

ll getMax( int a, int b ){
	int nas = -INF;
	for( int i = st-1 ; i>=0 ; i-- ){
		if( dep[a] - dep[b] >= (1<<i)){
			nas = std::max( nas, maxLca[a][i] );
			a = lca[a][i];
		}
	}
	return nas;
}

int main () {

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

	int n, m, q;
	std::cin>>n>>m>>q;

	for( int i=0 ; i<=n ; i++ ){par[i] = i; sz[i] =1;}

	for( int i=m ; i>=1 ; i-- ){
		int a = i;
	//	std::cerr<<i<<" , "<<m-i+1<<":\n";
		for( int j=2 ; i*j <= n ; j++ ){
			int b = i*j;
			if( get( a ) != get(b) ){
	//			std::cerr<<a<<" -> "<<b<<"\n";
				uni(a, b);
				v[a].push_back({b, m-i+1});
				v[b].push_back({a, m-i+1});
			}
		}
	//	std::cerr<<"\n";
	}

	dfs( 1 );
	
	st = 0;
	while( true ){
		st++;
		if( (1<<st) > n ) break;
		for( int i=1 ; i<=n ; i++ ){
			lca[i][st] = lca[lca[i][st-1]][st-1];
			maxLca[i][st] = std::max( maxLca[lca[i][st-1]][st-1], maxLca[i][st-1]);
		}
	}

	while( q-- ){
		int a, b;
		std::cin>>a>>b;
		int lc = getLca( a, b );
	//	std::cerr<<" ! "<<lc<<"\n";
		ll nas = std::max( getMax( a, lc ), getMax( b, lc ) );
		std::cout<<nas<<"\n";
	}

	return 0;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 3660 KB Output is correct
2 Correct 26 ms 3648 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 4152 KB Output is correct
2 Correct 32 ms 4040 KB Output is correct

Subtask #5
14.0 / 14.0

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

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 12400 KB Output is correct
2 Correct 58 ms 13708 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 16908 KB Output is correct
2 Correct 63 ms 17428 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 90 ms 21880 KB Output is correct
2 Correct 100 ms 23908 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 26424 KB Output is correct
2 Correct 120 ms 29784 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 32844 KB Output is correct
2 Correct 139 ms 33016 KB Output is correct