Submission #1122152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122152		inksamurai	Pictionary (COCI18_pictionary)	C++17	140 / 140	201 ms	10176 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<pii> qry(q);
	for(int i = 0; i < q; i++){
		qry[i] = {1, m};
	}
	
	vector<pii> ask(q);
	for(int i = 0; i < q; i++){
		int u, v;
		cin >> u >> v;
		ask[i] = {u, v};	
	}
	
	vector<int> answer(q, m);
	for(int iter = 0; iter < 20; iter++){
		vector <vector<int>> adqry(m + 1);
		for(int i = 0; i < q; i++){
			int md = (qry[i].fi + qry[i].se) / 2;			
//			cout << qry[i].fi << " " << qry[i].se << " " << md << "\n";
			adqry[md].push_back(i);
		}
		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 = 2 * x; y <= n; y += x){
				merge(x, y);
			}
//			if(iter == 2){
//				cout << get_parent(9) << " " << get_parent(20) << "\n";
//			}
			for(int id : adqry[i]){
				int u = ask[id].fi;
				int v = ask[id].se;
				if(get_parent(u) == get_parent(v)){
//					cout << i << "\n";
					answer[id] = i;
					qry[id].se = i - 1;
				} else {
					qry[id].fi = i + 1;
				}
			}
		}
	}
	
	for(int i = 0; i < q; i++){
		cout << answer[i] << "\n";
	}
}

• 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