Submission #382579

#	Time	Username	Problem	Language	Result	Execution time	Memory
382579		rainboy	Bridges (APIO19_bridges)	C11	0 / 100	3054 ms	4228 KiB

bridges

#include <stdio.h>

#define N	50000
#define M	100000

int ds[N], sz[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, sz[j] += sz[i];
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, sz[i] += sz[j];
	}
}

int main() {
	static int ii[M], jj[M], ww[M];
	int n, m, q, h, i;

	scanf("%d%d", &n, &m);
	for (h = 0; h < m; h++)
		scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
	scanf("%d", &q);
	while (q--) {
		int t, w;

		scanf("%d", &t);
		if (t == 1) {
			scanf("%d%d", &h, &w), h--;
			ww[h] = w;
		} else {
			scanf("%d%d", &i, &w), i--;
			for (i = 0; i < n; i++)
				ds[i] = -1, sz[i] = 1;
			for (h = 0; h < m; h++)
				if (w <= ww[h])
					join(ii[h], jj[h]);
			printf("%d\n", sz[find(i)]);
		}
	}
	return 0;
}

Compilation message (stderr)

bridges.c: In function 'main':
bridges.c:30:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   30 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
bridges.c:32:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   32 |   scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.c:33:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   33 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
bridges.c:37:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   37 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
bridges.c:39:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   39 |    scanf("%d%d", &h, &w), h--;
      |    ^~~~~~~~~~~~~~~~~~~~~
bridges.c:42:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   42 |    scanf("%d%d", &i, &w), i--;
      |    ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27