Submission #529922

#	Time	Username	Problem	Language	Result	Execution time	Memory
529922		lunchbox	Bridges (APIO19_bridges)	C11	100 / 100	1895 ms	8072 KiB

bridges

#include <stdio.h>
#include <string.h>
#include <sys/time.h>
 
#define N	50000
#define M	100000
#define Q	100000
#define B	1000
 
unsigned int X;
 
void srand_() {
	struct timeval tv;
 
	gettimeofday(&tv, NULL);
	X = tv.tv_sec ^ tv.tv_usec | 1;
}
 
int rand_() {
	return (X *= 3) >> 1;
}
 
int *aa;
 
void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
 
		while (j < k) {
			int c = aa[i_] - aa[ii[j]];
 
			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}
 
struct R {
	int i, j, i_ds, j_ds;
} rr[N];
 
int ds[N], r_cnt;
 
int find(int i) {
	return ds[i] < 0 ? i : find(ds[i]);
}
 
int join(int i, int j, int r) {
	int k;
 
	i = find(i), j = find(j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		k = i, i = j, j = k;
	if (r)
		rr[r_cnt].i = i, rr[r_cnt].j = j, rr[r_cnt].i_ds = ds[i], rr[r_cnt].j_ds = ds[j], r_cnt++;
	ds[i] += ds[j], ds[j] = i;
	return 1;
}
 
int main() {
	int n, m, q, h, i, j, k, u_cnt, q_cnt;
	static int hh[M], ii[M], jj[M], ww[M], ww_[M], changed[M];
	static int q_ii[Q], q_ww[Q], uu[Q], qq[Q], ans[Q];
 
	srand_();
	r_cnt = u_cnt = q_cnt = 0;
	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]--;
		hh[h] = h;
	}
	scanf("%d", &q);
	for (h = 0; h < q; h++) {
		int t;
 
		scanf("%d%d%d", &t, &q_ii[h], &q_ww[h]), q_ii[h]--;
		if (t == 1)
			uu[u_cnt++] = h;
		else
			qq[q_cnt++] = h;
		if ((h + 1) % B == 0 || h + 1 == q) {
			aa = ww, sort(hh, 0, m);
			aa = q_ww, sort(qq, 0, q_cnt);
			memset(ds, -1, n * sizeof *ds);
			memset(changed, 0, m * sizeof *changed);
			for (i = 0; i < u_cnt; i++)
				changed[q_ii[uu[i]]] = 1;
			j = 0;
			for (i = 0; i < q_cnt; i++) {
				while (j < m && ww[hh[j]] >= q_ww[qq[i]]) {
					if (changed[hh[j]] == 0)
						join(ii[hh[j]], jj[hh[j]], 0);
					j++;
				}
				for (k = 0; k < u_cnt; k++)
					ww_[q_ii[uu[k]]] = ww[q_ii[uu[k]]];
				for (k = 0; k < u_cnt; k++)
					if (uu[k] < qq[i])
						ww_[q_ii[uu[k]]] = q_ww[uu[k]];
				for (k = 0; k < u_cnt; k++)
					if (ww_[q_ii[uu[k]]] >= q_ww[qq[i]])
						join(ii[q_ii[uu[k]]], jj[q_ii[uu[k]]], 1);
				ans[qq[i]] = -ds[find(q_ii[qq[i]])];
				while (r_cnt > 0) {
					r_cnt--;
					ds[rr[r_cnt].i] = rr[r_cnt].i_ds;
					ds[rr[r_cnt].j] = rr[r_cnt].j_ds;
				}
			}
			for (i = 0; i < u_cnt; i++)
				ww[q_ii[uu[i]]] = q_ww[uu[i]];
			u_cnt = 0;
			q_cnt = 0;
		}
	}
	for (h = 0; h < q; h++)
		if (ans[h] > 0)
			printf("%d\n", ans[h]);
	return 0;
}

Compilation message (stderr)

bridges.c: In function 'srand_':
bridges.c:16:16: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   16 |  X = tv.tv_sec ^ tv.tv_usec | 1;
      |      ~~~~~~~~~~^~~~~~~~~~~~
bridges.c: In function 'main':
bridges.c:78:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
bridges.c:80:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.c:83:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
bridges.c:87:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf("%d%d%d", &t, &q_ii[h], &q_ww[h]), q_ii[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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