Submission #382621

#	Time	Username	Problem	Language	Result	Execution time	Memory
382621		rainboy	Bridges (APIO19_bridges)	C11	16 / 100	103 ms	4460 KiB

bridges

#include <stdio.h>

#define N	50000
#define M	100000
#define N_	(1 << 16)	/* N_ = pow2(ceil(log2(N))) */

int min(int a, int b) { return a < b ? a : b; }

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 st[N_ * 2], n_;

void pul(int i) {
	st[i] = min(st[i << 1 | 0], st[i << 1 | 1]);
}

void build(int *aa, int n) {
	int i;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++)
		st[n_ + i] = i < n ? aa[i] : -1;
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void update(int i, int x) {
	st[i += n_] = x;
	while (i > 1)
		pul(i >>= 1);
}

int query_l(int r, int x) {
	int l = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0) {
			if (st[r] < x) {
				while (r < n_)
					r = st[r << 1 | 1] < x ? r << 1 | 1 : r << 1 | 0;
				return r - n_;
			}
			r--;
		}
	return -1;
}

int query_r(int l, int x) {
	int r = n_ - 1;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1) {
			if (st[l] < x) {
				while (l < n_)
					l = st[l << 1 | 0] < x ? l << 1 | 0 : l << 1 | 1;
				return l - n_;
			}
			l++;
		}
	return n_;
}

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

	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);
	if (n <= 1000 && m <= 1000 && q <= 100000 && 0) {
		while (q--) {
			int t, w;

			scanf("%d", &t);
			if (t == 1) {
				scanf("%d%d", &h, &w), h--;
				ww[h] = w;
			} else {
				int s, i;

				scanf("%d%d", &s, &w), s--;
				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(s)]);
			}
		}
	} else {
		build(ww, n - 1);
		while (q--) {
			int t, w;

			scanf("%d", &t);
			if (t == 1) {
				scanf("%d%d", &h, &w), h--;
				update(h, w);
			} else {
				int s;

				scanf("%d%d", &s, &w), s--;
				printf("%d\n", query_r(s, w) - query_l(s - 1, w));
			}
		}
	}
	return 0;
}

Compilation message (stderr)

bridges.c: In function 'main':
bridges.c:87:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   87 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
bridges.c:89:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   89 |   scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.c:90:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   90 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
bridges.c:95:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   95 |    scanf("%d", &t);
      |    ^~~~~~~~~~~~~~~
bridges.c:97:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   97 |     scanf("%d%d", &h, &w), h--;
      |     ^~~~~~~~~~~~~~~~~~~~~
bridges.c:102:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  102 |     scanf("%d%d", &s, &w), s--;
      |     ^~~~~~~~~~~~~~~~~~~~~
bridges.c:116:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  116 |    scanf("%d", &t);
      |    ^~~~~~~~~~~~~~~
bridges.c:118:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  118 |     scanf("%d%d", &h, &w), h--;
      |     ^~~~~~~~~~~~~~~~~~~~~
bridges.c:123:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  123 |     scanf("%d%d", &s, &w), s--;
      |     ^~~~~~~~~~~~~~~~~~~~~

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