제출 #1122144

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122144		inksamurai	Pictionary (COCI18_pictionary)	C++17	28 / 140	1567 ms	2900 KiB

pictionary

#include <bits/stdc++.h>

using namespace std;

int par[300000], siz[300000];

int get_parent(int v){
	if(v == par[v]){
		return v;
	}
	return par[v] = get_parent(par[v]);
}

void merge(int u, int v){
	int parent_u = get_parent(u);
	int parent_v = get_parent(v);
	if(parent_u == parent_v) return;
	if(siz[parent_u] < siz[parent_v]){
		swap(parent_u, parent_v);
	}
	par[parent_v] = parent_u;
	siz[parent_u] += siz[parent_v];
}

bool ask(int n, int m, int j, int u, int v){
	for(int i = 0; i <= n; i++){
		par[i] = i;
		siz[i] = 1;
	}
	for(int i = 1; i <= j; i++){
		int x = m - i + 1;
		for(int y = 2 * x; y <= n; y += x){
			merge(x, y);
		}
	}
	if(get_parent(u) == get_parent(v)){
		return true;
	}
	return false;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	
	int n, m, q;
	cin >> n >> m >> q;
	
	for(int i = 0; i < q; i++){
		int u, v;
		cin >> u >> v;
		
		int l = 1, r = m;
		int opt = m;
		while(l <= r){
			int md = (l + r) / 2;
			if(ask(n, m, md, u, v)){
				opt = md, r = md - 1;
			} else {
				l = md + 1;
			}
		}
		cout << opt << "\n";
	}
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14