제출 #1122154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122154		inksamurai	Pictionary (COCI18_pictionary)	C++17	0 / 140	82 ms	9288 KiB

pictionary

#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second

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;
	
	vector<vector<pii>> adqry(n + 1);
	for(int i = 0; i < q; i++){
		int u, v;
		cin >> u >> v;
		adqry[u].push_back({i, v});
		adqry[v].push_back({i, u});
	}
	
	vector<int> answer(q, m);
	for(int i = 0; i <= n; i++){
		par[i] = i;
		siz[i] = 1;
	}
	for(int i = 1; i <= m; i++){
		int x = m - i + 1;
		for(int y = x; y <= n; y += x){
			merge(x, y);
			for(pair<int,int> p : adqry[y]){
				int id = p.fi;
				int z = p.se;
				if(get_parent(y) == get_parent(z)){
					answer[id] = min(answer[id], i);
				}
			}
		}
	}
	
	for(int i = 0; i < q; i++){
		cout << answer[i] << "\n";
	}
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 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