Submission #200178

#	Time	Username	Problem	Language	Result	Execution time	Memory
200178		Saboon	Pictionary (COCI18_pictionary)	C++14	140 / 140	335 ms	27856 KiB

pictionary

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

const int maxn = 1e5 + 37;

vector<int> mult[maxn];
int c[maxn], ans[maxn], par[maxn];
set<int> s[maxn];

int get_par(int v){
	return par[v] < 0 ? v : par[v] = get_par(par[v]);
}

void merge(int v, int u, int idx){
	if ((v = get_par(v)) == (u = get_par(u)))
		return;
	if (s[c[v]].size() > s[c[u]].size())
		swap(v, u);
	par[v] = u;
	for (auto it : s[c[v]]){
		if (s[c[u]].find(it) != s[c[u]].end()){
			ans[it] = idx;
			s[c[u]].erase(it);
			continue;
		}
		s[c[u]].insert(it);
	}
	s[c[v]].clear();
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j += i)
			mult[i].push_back(j);
	for (int i = 1; i <= n; i++)
		c[i] = i, par[i] = -1;
	for (int i = 1; i <= q; i++){
		int v, u;
		cin >> v >> u;
		s[c[v]].insert(i);
		s[c[u]].insert(i);
	}
	for (int i = m; i >= 1; i--){
		for (int j = 1; j < mult[i].size(); j++){
			int x = mult[i][j - 1], y = mult[i][j];
			merge(x, y, m - i + 1);
		}
	}
	for (int i = 1; i <= q; i++)
		cout << ans[i] << '\n';
}

Compilation message (stderr)

pictionary.cpp: In function 'int main()':
pictionary.cpp:48:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < mult[i].size(); j++){
                   ~~^~~~~~~~~~~~~~~~

• 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