Submission #719383

#	Time	Username	Problem	Language	Result	Execution time	Memory
719383		Doncho_Bonboncho	Pictionary (COCI18_pictionary)	C++14	140 / 140	156 ms	33016 KiB

pictionary

#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 / 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