Submission #924333

#	Time	Username	Problem	Language	Result	Execution time	Memory
924333		rainboy	트리 (KOI16_treeM)	C11	100 / 100	120 ms	13448 KiB

tree

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

#define N	200000
#define Q	400000

int ds[N];

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

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

int main() {
	static int pp[N], tt[Q], ii[Q], jj[Q];
	static char yes[Q];
	int n, q, h, i;

	scanf("%d%d", &n, &q), q += n - 1;
	for (i = 1; i < n; i++)
		scanf("%d", &pp[i]), pp[i]--;
	for (h = 0; h < q; h++) {
		scanf("%d", &tt[h]);
		if (tt[h] == 0)
			scanf("%d", &ii[h]), ii[h]--;
		else
			scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
	}
	memset(ds, -1, n * sizeof *ds);
	for (h = q - 1; h >= 0; h--)
		if (tt[h] == 1)
			yes[h] = find(ii[h]) == find(jj[h]);
		else
			join(ii[h], pp[ii[h]]);
	for (h = 0; h < q; h++)
		if (tt[h] == 1)
			printf(yes[h] ? "YES\n": "NO\n");
	return 0;
}

Compilation message (stderr)

tree.c: In function 'main':
tree.c:32:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d%d", &n, &q), q += n - 1;
      |  ^~~~~~~~~~~~~~~~~~~~~
tree.c:34:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d", &pp[i]), pp[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
tree.c:36:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   scanf("%d", &tt[h]);
      |   ^~~~~~~~~~~~~~~~~~~
tree.c:38:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |    scanf("%d", &ii[h]), ii[h]--;
      |    ^~~~~~~~~~~~~~~~~~~
tree.c:40:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |    scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 29 / 29