제출 #383051

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
383051		rainboy	다리 (APIO19_bridges)	C11	59 / 100	3090 ms	8812 KiB

bridges

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

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

unsigned int X = 12345;

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

int ds[N], rep[N], sz[N];

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

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

int ii[M], jj[M], ww[M + Q];
int tt[Q], idx[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;
}

int id[N], inv[N];
int ii_[B][B * 2], cnt[B]; char visited[B * 2];

void dfs(int i, int w_, int h) {
	int o;

	if (visited[i])
		return;
	visited[i] = 1;
	ii_[h][cnt[h]++] = inv[i];
	for (o = eo[i]; o--; ) {
		int j = ej[i][o], w = ww[eh[i][o]];

		if (w <= w_)
			dfs(j, w_, h);
	}
}

int main() {
	static int hh[M + Q], 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], &idx[h], &ww[m + h]), idx[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;
	for (g = 0; g * B < q; g++) {
		int l = g * B, r = min((g + 1) * B, q), n_;

		memset(hh, -1, (m + q) * sizeof *hh);
		for (h = 0; h < m; h++)
			hh[ww[h]] = h;
		memset(id, -1, n * sizeof *id);
		memset(eo, 0, B * 2 * sizeof *eo);
		for (h = l, n_ = 0; h < r; h++)
			if (tt[h] == 1) {
				int h_ = idx[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 = idx[h];
				if (id[i] == -1)
					inv[id[i] = n_++] = i;
				hh[ww[m + h]] = m + h;
			}
		for (i = 0; i < n; i++)
			ds[i] = -1, rep[i] = id[i];
		for (w = 0; w < m + q; w++) {
			h = hh[w];
			if (h != -1 && h < m) {
				i = find(ii[h]), j = find(jj[h]);
				if (i != j) {
					type[h] = rep[i] != -1 && rep[j] != -1 ? -1 : 1;
					join(i, j);
				} else
					type[h] = 0;
			}
		}
		for (i = 0; i < n; i++)
			ds[i] = -1, rep[i] = id[i];
		for (w = 0; w < m + q; w++) {
			h = hh[w];
			if (h != -1 && h < m && type[h]) {
				i = find(ii[h]), j = find(jj[h]);
				if (type[h] == -1) {
					i = rep[i], j = rep[j];
					append(i, j, h), append(j, i, h);
				} else
					join(i, j);
			}
		}
		for (h = l; h < r; h++)
			if (tt[h] == 1) {
				int h_ = idx[h];

				ww[h_] = ww[m + h];
			} else {
				int h_;

				i = idx[h];
				cnt[h - l] = 0, dfs(id[i], ww[m + h], h - l);
				for (h_ = 0; h_ < cnt[h - l]; h_++)
					visited[id[ii_[h - l][h_]]] = 0;
			}
		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) {
					if (type[h] == 1) {
						i = find(ii[h]), j = find(jj[h]);
						if (i != j) {
							sz[i] = sz[j] = sz[i] + sz[j];
							join(i, j);
						}
					}
				} else {
					h -= m;
					while (cnt[h - l]--)
						ans[h] += sz[find(ii_[h - l][cnt[h - l]])];
				}
			}
	}
	for (h = 0; h < q; h++)
		if (tt[h] == 2)
			printf("%d\n", ans[h]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bridges.c: In function 'main':
bridges.c:102:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  102 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
bridges.c:104:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  104 |   scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.c:105:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  105 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
bridges.c:107:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  107 |   scanf("%d%d%d", &tt[h], &idx[h], &ww[m + h]), idx[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