Submission #40398

#	Time	Username	Problem	Language	Result	Execution time	Memory
40398		szawinis	Pictionary (COCI18_pictionary)	C++14	140 / 140	430 ms	27188 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+2;

int n, m, q, a[N], b[N], l[N], r[N], dsu[N];
vector<int> ls[N];
int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); }
void merge(int u, int v) {
	if((u = root(u)) == (v = root(v))) return;
	if(dsu[u] > dsu[v]) swap(u, v);
	dsu[u] += dsu[v];
	dsu[v] = u;
}
int main() {
	scanf("%d %d %d", &n, &m, &q);
	for(int i = 0; i < q; i++) cin >> a[i] >> b[i];
	fill(l, l+q, 0);
	fill(r, r+q, m);
	for(int iter = 18; iter >= 0; iter--) {
		for(int i = 0; i < q; i++) if(l[i] < r[i])
			ls[m - (l[i] + r[i] >> 1) + 1].push_back(i);

		fill(dsu+1, dsu+n+1, -1);
		for(int i: ls[m+1]) {
			int mid = l[i] + r[i] >> 1;
			if(root(a[i]) != root(b[i])) l[i] = mid+1;
			else r[i] = mid;
		}
		ls[m+1].clear();
		for(int x = m; x >= 1; x--) {
			for(int y = 2*x; y <= n; y += x) merge(x, y);
			for(int i: ls[x]) {
				int mid = l[i] + r[i] >> 1;
				if(root(a[i]) != root(b[i])) l[i] = mid+1;
				else r[i] = mid;
			}
			ls[x].clear();
		}
	}
	for(int i = 0; i < q; i++) printf("%d\n", l[i]);
}

Compilation message (stderr)

pictionary.cpp: In function 'int main()':
pictionary.cpp:21:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    ls[m - (l[i] + r[i] >> 1) + 1].push_back(i);
                 ^
pictionary.cpp:25:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = l[i] + r[i] >> 1;
                   ^
pictionary.cpp:33:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l[i] + r[i] >> 1;
                    ^
pictionary.cpp:15:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &q);
                               ^

• 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