Submission #382985

#	Time	Username	Problem	Language	Result	Execution time	Memory
382985		rainboy	Bridges (APIO19_bridges)	C11	73 / 100	3091 ms	8740 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 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], 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];
int *es[B * 2], *ew[B * 2], eo_[B * 2];

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

	if (o >= 2 && (o & o - 1) == 0) {
		ek[i] = (int *) realloc(ek[i], o * 2 * sizeof *ek[i]);
		ev[i] = (int *) realloc(ev[i], o * 2 * sizeof *ev[i]);
	}
	ek[i][o] = k, ev[i][o] = v;
}

int query(int i, int w_) {
	int lower = -1, upper = eo_[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[N]; int cnt;

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

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

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

int main() {
	static int hh[M + Q], id[N], ans[Q];
	static char type[M];
	int n, m, q, g, h, i, j, w, offline;

	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);
	offline = 1;
	for (h = 0; h < q; h++) {
		scanf("%d%d%d", &tt[h], &ii_[h], &ww[m + h]), ii_[h]--;
		if (tt[h] == 1)
			offline = 0;
	}
	for (h = 0; h < m + q; h++)
		hh[h] = h;
	sort(hh, 0, m + q);
	if (offline) {
		for (i = 0; i < n; i++)
			ds[i] = -1, sz[i] = 1;
		for (h = 0; h < m + q; h++) {
			int h_ = hh[h];

			if (h_ < m) {
				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;
				ans[h_] = sz[find(ii_[h_])];
			}
		}
		for (h = 0; h < q; h++)
			printf("%d\n", ans[h]);
	} else {
		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_ = ii_[h];

					i = ii[h_], j = jj[h_], w = ww[h_];
					hh[w] = -1;
					if (id[i] == -1)
						id[i] = n_++;
					if (id[j] == -1)
						id[j] = n_++;
				} else {
					i = ii_[h];
					if (id[i] == -1)
						id[i] = n_++;
				}
			for (i = 0; i < n_; i++) {
				ej[i] = (int *) malloc(2 * sizeof *ej[i]), eh[i] = (int *) malloc(2 * sizeof *eh[i]), eo[i] = 0;
				es[i] = (int *) malloc(2 * sizeof *es[i]), ew[i] = (int *) malloc(2 * sizeof *ew[i]), eo_[i] = 0;
			}
			for (i = 0; i < n; i++)
				ds[i] = -1, rep[i] = id[i];
			memset(type, 0, m * sizeof *type);
			for (w = 0; w < m + q; w++)
				if ((h = hh[w]) != -1) {
					i = find(ii[h]), j = find(jj[h]);
					if (i != j) {
						type[h] = rep[i] != -1 && rep[j] != -1 ? -1 : 1;
						join(i, j);
					}
				}
			for (i = 0; i < n; i++)
				ds[i] = -1, rep[i] = id[i], sz[i] = 1;
			memset(eo_, 0, B * 2 * sizeof *eo_);
			for (w = 0; w < m + q; w++)
				if ((h = hh[w]) != -1 && type[h]) {
					i = find(ii[h]), j = find(jj[h]);
					if (type[h] == -1) {
						i = rep[i], j = rep[j];
						append(ej, eh, eo, i, j, h), append(ej, eh, eo, j, i, h);
					} else {
						sz[i] = sz[j] = sz[i] + sz[j];
						if (rep[i] != -1)
							append(es, ew, eo_, rep[i], sz[i], w);
						if (rep[j] != -1)
							append(es, ew, eo_, rep[j], sz[j], w);
						join(i, j);
					}
				}
			for (h = 0; h < m; h++)
				if (hh[ww[h]] == -1) {
					i = id[ii[h]], j = id[jj[h]];
					append(ej, eh, eo, i, j, h), append(ej, eh, eo, j, i, h);
				}
			for (h = l; h < r; h++)
				if (tt[h] == 1) {
					int h_ = ii_[h];

					ww[h_] = ww[m + h];
				} else {
					i = ii_[h];
					memset(visited, 0, B * 2 * sizeof *visited);
					cnt = 0, dfs(id[i], ww[m + h]);
					printf("%d\n", cnt);
				}
			for (i = 0; i < n_; i++) {
				free(ej[i]), free(eh[i]);
				free(es[i]), free(ew[i]);
			}
		}
	}
	return 0;
}

Compilation message (stderr)

bridges.c: In function 'append':
bridges.c:69:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   69 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
bridges.c: In function 'main':
bridges.c:112:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  112 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
bridges.c:114:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  114 |   scanf("%d%d%d", &ii[h], &jj[h], &ww[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.c:115:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  115 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
bridges.c:118:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  118 |   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: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27