Submission #119118

#	Time	Username	Problem	Language	Result	Execution time	Memory
119118		SuperJava	Pictionary (COCI18_pictionary)	C++17	140 / 140	621 ms	43208 KiB

pictionary

//fold
#ifndef KHALIL
#include <bits/stdc++.h>
#else
#include "header.h"
#endif
#define endl '\n'
#define mp make_pair
#define tostr(x) static_cast<ostringstream&>((ostringstream()<<dec<<x)).str()
#define rep(i,begin,end) for(auto i = begin;i < end;i++)
#define repr(i,begin,end) for(auto i = begin-1;i >= end;i--)
#define pb push_back
#define sz(a) ((int)(a).size())
#define fi first
#define se second
#define abs(a) ((a) < (0) ? (-1)*(a) : (a))
#define SQ(a) ((a)*(a))
#define eqd(a,b) (abs(a-b)<1e-9)
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename t> t in(t q){cin >> q;return q;}
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v){os << "[";for (int i = 0; i < sz(v); ++i) { os << v[i]; if (i != sz(v) - 1) os << ",";}os << "]";return os;}
template <typename T> ostream& operator<<(ostream& os, const set<T>& v){os << "[";for (auto i = v.begin(); i != v.end();) { os << *i; i++; if (i != v.end()) os << ",";}os << "]";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const map<T, S>& v){for (auto it : v)os << "(" << it.first << ":" << it.second << ")";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const pair<T, S>& v){os << "(" << v.first << "," << v.second << ")";return os;}
const long double PI = acosl(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
//endfold
#define  N  (100'005)
#define MOD (1'000'000'007ll)
#define OO (1'050'000'000)
#define OOL (1'100'000'000'000'000'000ll)

//global
int ans[N];

struct component{
	int par;
	int sz;
	set<int> numbers;
	map<int,vector<int>> requests;
};

component dsu[N];

int home(int u){
	if(dsu[u].par == u) return u;
	dsu[u].par = home(dsu[u].par);
	return dsu[u].par;
}

void merge(int u,int v,int c){
	u = home(u); v = home(v);
	if(u == v) return;
//	cout << u << ": " << dsu[u].requests << "," << dsu[u].numbers << endl;
//	cout << v << ": " << dsu[v].requests << "," << dsu[v].numbers << endl;
	if(sz(dsu[u].requests) <= sz(dsu[v].numbers)){
		vector<int> tbd;
		for(auto el:dsu[u].requests){
			if(dsu[v].numbers.count(el.first)){
				tbd.push_back(el.first);
				for(int id:el.second){
					ans[id] = c;
				}
			}
		}
		for(int el:tbd) dsu[u].requests.erase(el);
	}else{
		vector<int> tbd;
		for(int tar:dsu[v].numbers){
			if(dsu[u].requests.count(tar)){
				tbd.push_back(tar);
				for(int id:dsu[u].requests[tar]){
					ans[id] = c;
				}
			}
		}
		for(int el:tbd) dsu[u].requests.erase(el);
	}
	if(sz(dsu[v].requests) <= sz(dsu[u].numbers)){
		vector<int> tbd;
		for(auto el:dsu[v].requests){
			if(dsu[u].numbers.count(el.first)){
				tbd.push_back(el.first);
				for(int id:el.second){
					ans[id] = c;
				}
			}
		}
		for(int el:tbd) dsu[v].requests.erase(el);
	}else{
		vector<int> tbd;
		for(int tar:dsu[u].numbers){
			if(dsu[v].requests.count(tar)){
				tbd.push_back(tar);
				for(int id:dsu[v].requests[tar]){
					ans[id] = c;
				}
			}
		}
		for(int el:tbd) dsu[v].requests.erase(el);
	}
	if(dsu[u].sz < dsu[v].sz) swap(u,v);
	for(int el:dsu[v].numbers) dsu[u].numbers.insert(el);
	for(auto el:dsu[v].requests)
		dsu[u].requests[el.first].insert(
			dsu[u].requests[el.first].end(),
			el.second.begin(), el.second.end()
		);
	dsu[u].sz += dsu[v].sz;
	dsu[v].par = u;
//	cout << u << "+" << v << ": " << dsu[u].requests << "," << dsu[u].numbers << endl;
//	cout << endl;
}

vector<int> coprime[330];

int main(){
	//fold
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cout << setprecision(10);
	//endfold
	int n,m,q;
	cin >> n >> m >> q;
	for (int i = 0; i < n; ++i){
		dsu[i+1] = {i+1,1,{i+1},{}};
	}
	rep(i,0,q){
		int u,v;
		cin >> u >> v;
		if(u > v) swap(u,v);
		dsu[u].requests[v].push_back(i);
	}
	rep(i,1,320){
		rep(j,i+1,320){
			if(__gcd(i,j) == 1) coprime[i].push_back(j);
		}
	}
	for (int i = m; i >= 320; --i){
		for(int j = 1; j*i <= n; j++){
			for(int k:coprime[j]){
				if(k*i > n) break;
				merge(i*j,i*k,m-i+1);
			}
		}
	}
	for (int i = min(m,319); i >= 1; --i){
		set<int> tm;
		for(int j = i; j <= n; j += i){
			tm.insert(home(j));
		}
		int fir = *tm.begin();
		for(int w:tm){
			if(w == fir) continue;
			merge(fir,w,m-i+1);
		}
	}
	rep(i,0,q){
		cout << ans[i] << endl;
	}
	return 0;
}

• 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