Submission #382626

#	Time	Username	Problem	Language	Result	Execution time	Memory
382626		rainboy	Bridges (APIO19_bridges)	C11	43 / 100	144 ms	8172 KiB

bridges

#include <stdio.h>

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

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

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

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 ii[M], jj[M], ii_[Q], ww[M + Q];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = ww[hh[j]] != ww[h] ? ww[h] - ww[hh[j]] : hh[j] - h;

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

int main() {
	static int hh[M + Q], ans[Q];
	int n, m, q, h, i, path;

	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]--;
	path = m == n - 1;
	for (h = 0; h < m; h++)
		if (ii[h] != h || jj[h] != h + 1) {
			path = 0;
			break;
		}
	scanf("%d", &q);
	if (n <= 1000 && m <= 1000 && q <= 100000) {
		while (q--) {
			int t, w;

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

				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 if (path) {
		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));
			}
		}
	} else {
		for (h = 0; h < q; h++) {
			int t;

			scanf("%d%d%d", &t, &ii_[h], &ww[m + h]), ii_[h]--;
		}
		for (h = 0; h < m + q; h++)
			hh[h] = h;
		sort(hh, 0, m + q);
		for (i = 0; i < n; i++)
			ds[i] = -1, sz[i] = 1;
		for (h = 0; h < m + q; h++) {
			int h_ = hh[h];

			if (h_ < m)
				join(ii[h_], jj[h_]);
			else {
				h_ -= m;
				ans[h_] = sz[find(ii_[h_])];
			}
		}
		for (h = 0; h < q; h++)
			printf("%d\n", ans[h]);
	}
	return 0;
}

Compilation message (stderr)

bridges.c: In function 'main':
bridges.c:118:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  118 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
bridges.c:120:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  120 |   scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.c:127:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  127 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
bridges.c:132:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  132 |    scanf("%d", &t);
      |    ^~~~~~~~~~~~~~~
bridges.c:134:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  134 |     scanf("%d%d", &h, &w), h--;
      |     ^~~~~~~~~~~~~~~~~~~~~
bridges.c:139:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  139 |     scanf("%d%d", &s, &w), s--;
      |     ^~~~~~~~~~~~~~~~~~~~~
bridges.c:153:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  153 |    scanf("%d", &t);
      |    ^~~~~~~~~~~~~~~
bridges.c:155:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  155 |     scanf("%d%d", &h, &w), h--;
      |     ^~~~~~~~~~~~~~~~~~~~~
bridges.c:160:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  160 |     scanf("%d%d", &s, &w), s--;
      |     ^~~~~~~~~~~~~~~~~~~~~
bridges.c:168:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  168 |    scanf("%d%d%d", &t, &ii_[h], &ww[m + h]), ii_[h]--;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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