제출 #383085

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

bridges

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

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

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];
int *es[B * 2], *ew[B * 2], eo1[B * 2], eo1_[B * 2];

void append(int **ek, int **ev, int *eo, int *eo_, int i, int k, int v) {
	int o = eo[i]++;

	if (o == eo_[i]) {
		eo_[i] *= 2;
		ek[i] = (int *) realloc(ek[i], eo_[i] * sizeof *ek[i]);
		ev[i] = (int *) realloc(ev[i], eo_[i] * sizeof *ev[i]);
	}
	ek[i][o] = k, ev[i][o] = v;
}

int query(int i, int w_) {
	int lower = -1, upper = eo1[i];

	while (upper - lower > 1) {
		int o = (lower + upper) / 2;

		if (ew[i][o] <= w_)
			lower = o;
		else
			upper = o;
	}
	return lower == -1 ? 1 : es[i][lower];
}

char visited[B * 2];

int solve(int i, int w_) {
	static int qu[B * 2];
	int head, cnt, ans;

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

		i = qu[cnt--, head++];
		ans += query(i, w_);
		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;
		}
	}
	while (head--)
		visited[qu[head]] = 0;
	return ans;
}

int main() {
	static int hh[M + Q], id[N], ds[N], ds_[N], rep[N], sz[N];
	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;
		eo1_[i] = 2;
		es[i] = (int *) malloc(2 * sizeof *es[i]), ew[i] = (int *) malloc(2 * sizeof *ew[i]), eo1[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);
		memset(eo1, 0, B * 2 * sizeof *eo1);
		for (h = l, n_ = 0; h < r; h++)
			if (tt[h] == 1) {
				int h_ = ii_[h];

				i = ii[h_], j = jj[h_], w = ww[h_];
				if (id[i] == -1)
					id[i] = n_++;
				if (id[j] == -1)
					id[j] = n_++;
				if (hh[w] != -1) {
					hh[w] = -1;
					i = id[i], j = id[j];
					append(ej, eh, eo, eo_, i, j, h_), append(ej, eh, eo, eo_, j, i, h_);
				}
			} else {
				i = ii_[h];
				if (id[i] == -1)
					id[i] = n_++;
			}
		memset(ds, -1, n * sizeof *ds);
		memset(ds_, -1, n * sizeof *ds_);
		for (i = 0; i < n; i++)
			rep[i] = id[i], sz[i] = 1;
		for (w = 0; w < m + q; w++)
			if ((h = hh[w]) != -1) {
				i = find(ds, ii[h]), j = find(ds, jj[h]);
				if (i != j) {
					if (rep[i] != -1 && rep[j] != -1) {
						i = rep[i], j = rep[j];
						if (find(ds_, i) != find(ds_, j)) {
							append(ej, eh, eo, eo_, i, j, h), append(ej, eh, eo, eo_, j, i, h);
							join(ds_, find(ds_, i), find(ds_, j));
						}
					} else {
						sz[i] = sz[j] = sz[i] + sz[j];
						if (rep[i] != -1)
							append(es, ew, eo1, eo1_, rep[i], sz[i], w);
						if (rep[j] != -1)
							append(es, ew, eo1, eo1_, rep[j], sz[j], w);
						rep[i] = rep[j] = rep[i] != -1 ? rep[i] : rep[j];
						join(ds, i, j);
					}
				}
			}
		for (h = l; h < r; h++)
			if (tt[h] == 1)
				ww[ii_[h]] = ww[m + h];
			else
				printf("%d\n", solve(id[ii_[h]], ww[m + h]));
	}
	return 0;
}

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

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