Submission #383150

#	Time	Username	Problem	Language	Result	Execution time	Memory
383150		rainboy	Bridges (APIO19_bridges)	C11	100 / 100	2303 ms	9380 KiB

bridges

/* https://oj.uz/submission/124660 (Benq) */
#include <stdio.h>
#include <stdlib.h>

#define N	50000
#define M	100000
#define Q	100000
#define M_	(M + Q)
#define B	512

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 *aa;

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)
			if (aa[hh[j]] == aa[h])
				j++;
			else if (aa[hh[j]] > aa[h]) {
				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 *ej[N], eo[N], eo_[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o == eo_[i])
		ej[i] = (int *) realloc(ej[i], (eo_[i] *= 2) * sizeof *ej[i]);
	ej[i][o] = j;
}

char visited[N]; int qu[N], cnt, n;
int ii[M_], jj[M_], ww[M_], ll[M_], rr[M_], hh[M_], m;
int ii_[Q], ww_[Q], hh_[Q], ans[Q], sum;

void dfs(int i) {
	int o;

	if (visited[i])
		return;
	visited[i] = 1;
	qu[cnt++] = i;
	sum += sz[i];
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs(j);
	}
}

void solve(int l, int r) {
	static int hh1[B * 2];
	int m_, g, g_, g1, i, j;

	sort(hh_, l, r + 1);
	for (i = 0; i < n; i++)
		ds[i] = -1, sz[i] = 1;
	m_ = 0;
	for (g = l, g_ = 0; g <= r && ww_[hh_[g]]; g++) {
		int h = hh_[g], h_;

		while (g_ < m && ww[hh[g_]] >= ww_[h]) {
			h_ = hh[g_++];
			if (ll[h_] <= l && r <= rr[h_])
				join(ii[h_], jj[h_]);
			else if (rr[h_] >= l && r >= ll[h_])
				hh1[m_++] = h_;
		}
		for (g1 = 0; g1 < m_; g1++) {
			h_ = hh1[g1];
			if (ll[h_] <= h && h <= rr[h_]) {
				i = find(ii[h_]), j = find(jj[h_]);
				append(i, j), append(j, i);
			}
		}
		cnt = 0, sum = 0, dfs(find(ii_[h]));
		while (cnt--)
			visited[qu[cnt]] = 0;
		ans[h] = sum;
		for (g1 = 0; g1 < m_; g1++) {
			h_ = hh1[g1];
			if (ll[h_] <= h && h <= rr[h_]) {
				i = find(ii[h_]), j = find(jj[h_]);
				eo[i] = eo[j] = 0;
			}
		}
	}
}

int main() {
	int m_, q, g, 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]--;
		hh[h] = h;
	}
	scanf("%d", &q);
	m_ = m;
	for (h = 0; h < q; h++) {
		int t;

		scanf("%d", &t);
		if (t == 1) {
			int h_, w;

			scanf("%d%d", &h_, &w), h_--;
			ii_[h] = -1;
			rr[hh[h_]] = h - 1;
			ii[m_] = ii[h_], jj[m_] = jj[h_], ww[m_] = w, ll[m_] = h, hh[h_] = m_++;
		} else
			scanf("%d%d", &ii_[h], &ww_[h]), ii_[h]--;
	}
	for (h = 0; h < m; h++)
		rr[hh[h]] = q - 1;
	m = m_;
	for (h = 0; h < m; h++)
		hh[h] = h;
	aa = ww, sort(hh, 0, m);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc((eo_[i] = 2) * sizeof *ej[i]);
	for (h = 0; h < q; h++)
		hh_[h] = h;
	aa = ww_;
	for (g = 0; g * B < q; g++)
		solve(g * B, min((g + 1) * B, q) - 1);
	for (h = 0; h < q; h++)
		if (ww_[h])
			printf("%d\n", ans[h]);
	return 0;
}

Compilation message (stderr)

bridges.c: In function 'main':
bridges.c:131:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  131 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
bridges.c:133:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  133 |   scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.c:136:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  136 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
bridges.c:141:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  141 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
bridges.c:145:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  145 |    scanf("%d%d", &h_, &w), h_--;
      |    ^~~~~~~~~~~~~~~~~~~~~~
bridges.c:150:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  150 |    scanf("%d%d", &ii_[h], &ww_[h]), 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