Submission #746222

#	Time	Username	Problem	Language	Result	Execution time	Memory
746222		Juan	Pictionary (COCI18_pictionary)	C++17	140 / 140	213 ms	3656 KiB

pictionary

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, INF = 0x3f3f3f3f;


struct node{
	int id, pai, edge, sz;
};

struct DSU{
	node v[maxn];

	void init(int n){
		for(int i = 1; i <= n; i++) v[i] = {i, i, INF, 1};
	}

	int find(int x){return (v[x].pai==x ? x : find(v[x].pai));}

	void join(int a, int b, int k){
		a = find(a), b = find(b);
		if(a==b) return;

		if(v[a].sz > v[b].sz) swap(a, b);
		v[a] = {a, b, k, v[a].sz};
		v[b].sz += v[a].sz;
	}

	void query(int a, int b){
		int ans = 0;
		while(a!=b){
			if(v[a].edge < v[b].edge) ans = max(ans, v[a].edge), a = v[a].pai;
			else ans = max(ans, v[b].edge), b = v[b].pai;
		}
		cout << ans << '\n';
	}
}dsu;


int main(){
	int n, m, q; cin >> n >> m >> q;
	dsu.init(n);

	for(int i = m; i >= 1; i--){
		for(int j = i+i; j <= n; j+=i) dsu.join(i, j, m-i+1);
	}

	while(q--){
		int a, b; cin >> a >> b;
		dsu.query(a, b);
	}
}

• 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