Submission #383077

#	Time	Username	Problem	Language	Result	Execution time	Memory
383077		rainboy	Bridges (APIO19_bridges)	C11	59 / 100	3051 ms	20204 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], 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[N]; int cnt;
int w_;
 
void dfs(int i) {
	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);
	}
}
 
int main() {
	static int hh[M + Q], id[N];
	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;
		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);
		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_++;
			}
		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(eo1, 0, B * 2 * sizeof *eo1);
		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, eo_, i, j, h), append(ej, eh, eo, eo_, j, i, h);
				} 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);
					join(i, j);
				}
			}
		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, w_ = ww[m + h], dfs(id[i]);
				printf("%d\n", cnt);
			}
	}
	return 0;
}

Compilation message (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