oj.uz

Submission #472997

# Submission time Handle Problem Language Result Execution time Memory
472997 2021-09-14T17:50:50 Z rainboy Pictionary (COCI18_pictionary) C
140 / 140
 59 ms 2884 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 460 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1092 KB Output is correct
2 Correct 25 ms 1056 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1476 KB Output is correct
2 Correct 38 ms 1348 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1144 KB Output is correct
2 Correct 25 ms 1100 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1356 KB Output is correct
2 Correct 24 ms 1352 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1732 KB Output is correct
2 Correct 27 ms 1428 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2064 KB Output is correct
2 Correct 44 ms 2232 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2452 KB Output is correct
2 Correct 57 ms 2532 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 2884 KB Output is correct
2 Correct 55 ms 2752 KB Output is correct