Submission #472997

#	Time	Username	Problem	Language	Result	Execution time	Memory
472997		rainboy	Pictionary (COCI18_pictionary)	C11	140 / 140	59 ms	2884 KiB

pictionary

#include <stdio.h>
#include <string.h>

#define N	100000

int ds[N + 1], dd[N + 1];

int find(int i) {
	return ds[i] < 0 ? i : find(ds[i]);
}

void join(int i, int j, int d) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j, dd[i] = d;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, dd[j] = d;
	}
}

int query(int i, int j) {
	int d = 0;

	while (i != j)
		if (dd[i] > dd[j])
			d = dd[i], i = ds[i];
		else
			d = dd[j], j = ds[j];
	return d;
}

int main() {
	int n, q, m, i, j, d;

	scanf("%d%d%d", &n, &m, &q);
	memset(ds, -1, (n + 1) * sizeof *ds);
	for (d = m; d >= 1; d--)
		for (i = d; i + d <= n; i += d)
			join(i, i + d, d);
	while (q--) {
		scanf("%d%d", &i, &j);
		printf("%d\n", m + 1 - query(i, j));
	}
	return 0;
}

Compilation message (stderr)

pictionary.c: In function 'main':
pictionary.c:40:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d%d%d", &n, &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
pictionary.c:46:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |   scanf("%d%d", &i, &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