oj.uz

Submission #200178

# Submission time Handle Problem Language Result Execution time Memory
200178 2020-02-05T15:39:07 Z Saboon Pictionary (COCI18_pictionary) C++14
140 / 140
 335 ms 27856 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8056 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 9464 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 14944 KB Output is correct
2 Correct 165 ms 15352 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 18680 KB Output is correct
2 Correct 263 ms 17528 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 14332 KB Output is correct
2 Correct 107 ms 14300 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 15592 KB Output is correct
2 Correct 112 ms 16172 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 18936 KB Output is correct
2 Correct 125 ms 16888 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 22692 KB Output is correct
2 Correct 235 ms 23028 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 24564 KB Output is correct
2 Correct 256 ms 25716 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 27856 KB Output is correct
2 Correct 335 ms 27748 KB Output is correct