Submission #1139451

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139451		vako_p	Pictionary (COCI18_pictionary)	C++20	140 / 140	121 ms	15400 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 1e5 + 5;
int n,m,q,ans[mxN],a[mxN],b[mxN],L[mxN],R[mxN];
vector<int> qq[mxN];

struct ds{
	vector<int> rank,par;
	
	void init(){
		rank.resize(mxN);
		par.resize(mxN);
	}	
	
	void clear(){
		for(int i = 0; i <= n; i++){
			rank[i] = 0;
			par[i] = i;
		}
	}
	
	ll find(ll at){
		if(par[at] == at) return at;
		par[at] = find(par[at]);
		return par[at];
	}
	
	void merge(ll p1, ll p2){
		p1 = find(p1); p2 = find(p2);
		if(p1 == p2) return;
		if(rank[p1] < rank[p2]) swap(p1, p2);
		par[p2] = p1;
		rank[p1] += (rank[p1] == rank[p2]);
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> q;
	ds s;
	s.init();
	for(int i = 0; i < q; i++){
		cin >> a[i] >> b[i];
		L[i] = 1;
		R[i] = m + 1;
		qq[1 + m / 2].pb(i);
	}
	for(int i1 = 0; i1 < 18; i1++){
		s.clear();
		for(int i = m; i >= 1; i--){
			for(int j = i + i; j <= n; j += i) s.merge(i, j);
			for(auto it : qq[i]){
				if(s.find(a[it]) == s.find(b[it])) L[it] = i;
				else R[it] = i;
			}
			qq[i].clear();
		}
		for(int i = 0; i < q; i++){
			if(R[i] - L[i] == 1) ans[i] = L[i];
			else qq[L[i] + (R[i] - L[i]) / 2].pb(i);
		}
	}
	for(int i = 0; i < q; i++) cout << m - ans[i] + 1 << '\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