Submission #383109

#	Time	Username	Problem	Language	Result	Execution time	Memory
383109		rainboy	다리 (APIO19_bridges)	C11	59 / 100	3070 ms	10476 KiB

bridges

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	50000
#define M	100000
#define Q	100000
#define B	768

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

unsigned int X = 12345;

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

int find(int *ds, int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds, ds[i]));
}

void join(int *ds, int i, int j) {
	if (ds[i] > ds[j]) {
		ds[i] = j;
	} else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

int ii[M], jj[M], ww[M + Q];
int tt[Q], ii_[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 *ej[B * 2], *eh[B * 2], eo[B * 2], eo_[B * 2];

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

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

char visited[B * 2];

int bfs(int *qu, int i, int w_) {
	int head, cnt;

	head = 0, cnt = 0;
	visited[i] = 1, qu[head + cnt++] = i;
	while (cnt) {
		int o;

		i = qu[cnt--, head++];
		for (o = eo[i]; o--; ) {
			int j = ej[i][o], w = ww[eh[i][o]];

			if (w <= w_ && !visited[j])
				visited[j] = 1, qu[head + cnt++] = j;
		}
	}
	cnt = head;
	while (head--)
		visited[qu[head]] = 0;
	return cnt;
}

int main() {
	static int hh[M + Q], id[N], inv[N], ds[N], ds_[B * 2], rep[N], sz[N], qu[B][B * 2], cnt[B], ans[Q];
	static char type[M];
	int n, m, q, g, h, i, j, w;

	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);
	for (h = 0; h < q; h++)
		scanf("%d%d%d", &tt[h], &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 < B * 2; i++) {
		eo_[i] = 2;
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eh[i] = (int *) malloc(2 * sizeof *eh[i]), eo[i] = 0;
	}
	for (h = 0; h < m + q; h++)
		ww[hh[h]] = h;
	memset(hh, -1, (m + q) * sizeof *hh);
	memset(id, -1, n * sizeof *id);
	for (g = 0; g * B < q; g++) {
		int l = g * B, r = min((g + 1) * B, q), n_, h_;

		for (h = 0; h < m; h++)
			hh[ww[h]] = h;
		memset(eo, 0, B * 2 * sizeof *eo);
		for (h = l, n_ = 0; h < r; h++)
			if (tt[h] == 1) {
				h_ = ii_[h], i = ii[h_], j = jj[h_], w = ww[h_];
				if (id[i] == -1)
					inv[id[i] = n_++] = i;
				if (id[j] == -1)
					inv[id[j] = n_++] = j;
				if (hh[w] != -1) {
					hh[w] = -1;
					i = id[i], j = id[j];
					append(i, j, h_), append(j, i, h_);
				}
			} else {
				i = ii_[h];
				if (id[i] == -1)
					inv[id[i] = n_++] = i;
				hh[ww[m + h]] = m + h;
			}
		memset(ds_, -1, B * 2 * sizeof *ds_);
		for (i = 0; i < n; i++)
			ds[i] = -1, rep[i] = id[i];
		for (w = 0; w < m + q; w++)
			if ((h = hh[w]) != -1 && h < m && ww[h] == w) {
				i = find(ds, ii[h]), j = find(ds, jj[h]);
				if (i != j) {
					if (rep[i] != -1 && rep[j] != -1) {
						type[h] = -1;
						i = rep[i], j = rep[j];
						if (find(ds_, i) != find(ds_, j)) {
							append(i, j, h), append(j, i, h);
							join(ds_, find(ds_, i), find(ds_, j));
						}
					} else {
						type[h] = 1;
						rep[i] = rep[j] = rep[i] != -1 ? rep[i] : rep[j];
						join(ds, i, j);
					}
				} else
					type[h] = 0;
			}
		for (h = l; h < r; h++)
			if (tt[h] == 1) {
				h_ = ii_[h];
				ww[h_] = ww[m + h];
			} else
				cnt[h - l] = bfs(qu[h - l], id[ii_[h]], ww[m + h]);
		for (i = 0; i < n; i++)
			ds[i] = -1, sz[i] = 1;
		for (w = 0; w < m + q; w++)
			if ((h = hh[w]) != -1) {
				if (h < m) {
					i = ii[h], j = jj[h];
					if (type[h] == 1) {
						i = find(ds, i), j = find(ds, j);
						sz[i] = sz[j] = sz[i] + sz[j];
						join(ds, i, j);
					}
				} else {
					h -= m;
					if (h >= l && h < r)
						for (h_ = 0; h_ < cnt[h - l]; h_++)
							ans[h] += sz[find(ds, inv[qu[h - l][h_]])];
				}
			}
		for (h = l; h < r; h++)
			if (tt[h] == 1) {
				h_ = ii_[h];
				id[ii[h_]] = id[jj[h_]] = -1;
			} else
				id[ii_[h]] = -1;
	}
	for (h = 0; h < q; h++)
		if (tt[h] == 2)
			printf("%d\n", ans[h]);
	return 0;
}

Compilation message (stderr)

bridges.c: In function 'main':
bridges.c:99:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   99 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
bridges.c:101:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  101 |   scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.c:102:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  102 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
bridges.c:104:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  104 |   scanf("%d%d%d", &tt[h], &ii_[h], &ww[m + h]), ii_[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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