Submission #1275378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275378		SmuggingSpun	Pictionary (COCI18_pictionary)	C++20	140 / 140	268 ms	2988 KiB

pictionary

#include<bits/stdc++.h>
#define taskname "E"
using namespace std;
const int lim = 1e5 + 5;
int n, m, q, p[lim], xq[lim], yq[lim];
namespace sub1{
	int find_set(int N){
		return N == p[N] ? N : p[N] = find_set(p[N]);
	}
	void merge(int u, int v){
		if((u = find_set(u)) != (v = find_set(v))){
			p[u] = v;
		}
	}
	void solve(){
		iota(p + 1, p + n + 1, 1);
		vector<int>ans(q + 1, -1);
		for(int i = m; i > 0; i--){
			for(int j = i << 1; j <= n; j += i){
				merge(i, j);
			}
			for(int j = 1; j <= q; j++){
				if(ans[j] == -1 && find_set(xq[j]) == find_set(yq[j])){
					ans[j] = m - i + 1;
				}
			}
		}
		for(int i = 1; i <= q; i++){
			cout << ans[i] << "\n";
		}	
	}
}
namespace sub2{
	int w[lim], sz[lim];
	int find_set(int N){
		while(N != p[N]){
			N = p[N];
		}
		return N;
	}
	void merge(int u, int v, int t){
		if((u = find_set(u)) != (v = find_set(v))){
			if(sz[u] > sz[v]){
				swap(u, v);
			}
			w[u] = t;
			sz[p[u] = v] += sz[u];
		}
	}
	int get_max(int u, int v){
		int ans = 0;
		while(u != v){
			if(w[u] > w[v]){
				swap(u, v);
			}
			ans = w[u];
			u = p[u];
		}
		return ans;
	}
	void solve(){
		iota(p + 1, p + n + 1, 1);
		fill(sz + 1, sz + n + 1, 1);
		memset(w, 0x3f, sizeof(w));
		for(int i = m; i > 0; i--){
			for(int j = i << 1; j <= n; j += i){
				merge(i, j, m - i + 1);
			}
		}		
		for(int i = 1; i <= q; i++){
			cout << get_max(xq[i], yq[i]) << "\n";
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> m >> q;
	for(int i = 1; i <= q; i++){
		cin >> xq[i] >> yq[i];
	}
	if(n <= 1000){
		sub1::solve();
	}
	else{
		sub2::solve();
	}
}

Compilation message (stderr)

pictionary.cpp: In function 'int main()':
pictionary.cpp:78:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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