Submission #872822

#	Time	Username	Problem	Language	Result	Execution time	Memory
872822		rainboy	Rigged Roads (NOI19_riggedroads)	C11	100 / 100	256 ms	45140 KiB

riggedroads

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

#define N	300000
#define M	300000

unsigned int X = 12345;

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

int ii[M], jj[M];
int *eh[N], eo[N];

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

	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

int ff[N], pp[N], dd[N];

void dfs(int f, int p, int i, int d) {
	int o;

	ff[i] = f, pp[i] = p, dd[i] = d;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ii[h] ^ jj[h];

		if (j != p) {
			ii[h] = i, jj[h] = j;
			dfs(h, i, j, d + 1);
		}
	}
}

int ds[N], rr[N];

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

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

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)
			if (hh[j] == h)
				j++;
			else if (hh[j] < h) {
				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 main() {
	static char tree[M];
	static int ww[M], hh[M];
	int n, m, cnt, g, h, i, j, w;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < m; h++)
		scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
	for (g = 0; g < n - 1; g++) {
		scanf("%d", &h), h--;
		tree[h] = 1;
		append(ii[h], h), append(jj[h], h);
	}
	dfs(-1, -1, 0, 0);
	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		rr[i] = i;
	for (h = 0, w = 0; h < m; h++)
		if (tree[h]) {
			if (!ww[h])
				ww[h] = ++w, join(ii[h], jj[h]);
		} else {
			i = ii[h], j = jj[h], cnt = 0;
			while ((i = rr[find(i)]) != (j = rr[find(j)]))
				if (dd[i] > dd[j])
					hh[cnt++] = ff[i], join(pp[i], i);
				else
					hh[cnt++] = ff[j], join(pp[j], j);
			sort(hh, 0, cnt);
			for (g = 0; g < cnt; g++)
				ww[hh[g]] = ++w;
			ww[h] = ++w;
		}
	for (h = 0; h < m; h++)
		printf("%d ", ww[h]);
	printf("\n");
	return 0;
}

Compilation message (stderr)

riggedroads.c: In function 'append':
riggedroads.c:20:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   20 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
riggedroads.c: In function 'main':
riggedroads.c:85:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
riggedroads.c:89:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.c:91:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   scanf("%d", &h), h--;
      |   ^~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32