Submission #872822

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
872822	2023-11-13T21:37:25 Z	rainboy	Rigged Roads (NOI19_riggedroads)	C	100 / 100	256 ms	45140 KB

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

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.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8536 KB	Output is correct
2	Correct	1 ms	8540 KB	Output is correct
3	Correct	1 ms	8540 KB	Output is correct

Subtask #2

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8536 KB	Output is correct
2	Correct	1 ms	8540 KB	Output is correct
3	Correct	1 ms	8540 KB	Output is correct
4	Correct	2 ms	8540 KB	Output is correct
5	Correct	2 ms	10588 KB	Output is correct
6	Correct	1 ms	8540 KB	Output is correct
7	Correct	1 ms	8540 KB	Output is correct
8	Correct	1 ms	8540 KB	Output is correct

Subtask #3

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	17036 KB	Output is correct
2	Correct	60 ms	20564 KB	Output is correct
3	Correct	63 ms	17168 KB	Output is correct
4	Correct	88 ms	30032 KB	Output is correct
5	Correct	93 ms	31060 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	26704 KB	Output is correct
2	Correct	41 ms	19104 KB	Output is correct
3	Correct	19 ms	13836 KB	Output is correct
4	Correct	44 ms	23636 KB	Output is correct
5	Correct	17 ms	13092 KB	Output is correct

Subtask #5

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	154 ms	39028 KB	Output is correct
2	Correct	133 ms	45140 KB	Output is correct
3	Correct	32 ms	19792 KB	Output is correct
4	Correct	63 ms	24404 KB	Output is correct
5	Correct	142 ms	44540 KB	Output is correct

Subtask #6

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	112 ms	30876 KB	Output is correct
2	Correct	54 ms	24600 KB	Output is correct
3	Correct	233 ms	39836 KB	Output is correct
4	Correct	172 ms	37452 KB	Output is correct
5	Correct	11 ms	10332 KB	Output is correct

Subtask #7

32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	8536 KB	Output is correct
2	Correct	1 ms	8540 KB	Output is correct
3	Correct	1 ms	8540 KB	Output is correct
4	Correct	2 ms	8540 KB	Output is correct
5	Correct	2 ms	10588 KB	Output is correct
6	Correct	1 ms	8540 KB	Output is correct
7	Correct	1 ms	8540 KB	Output is correct
8	Correct	1 ms	8540 KB	Output is correct
9	Correct	33 ms	17036 KB	Output is correct
10	Correct	60 ms	20564 KB	Output is correct
11	Correct	63 ms	17168 KB	Output is correct
12	Correct	88 ms	30032 KB	Output is correct
13	Correct	93 ms	31060 KB	Output is correct
14	Correct	61 ms	26704 KB	Output is correct
15	Correct	41 ms	19104 KB	Output is correct
16	Correct	19 ms	13836 KB	Output is correct
17	Correct	44 ms	23636 KB	Output is correct
18	Correct	17 ms	13092 KB	Output is correct
19	Correct	154 ms	39028 KB	Output is correct
20	Correct	133 ms	45140 KB	Output is correct
21	Correct	32 ms	19792 KB	Output is correct
22	Correct	63 ms	24404 KB	Output is correct
23	Correct	142 ms	44540 KB	Output is correct
24	Correct	112 ms	30876 KB	Output is correct
25	Correct	54 ms	24600 KB	Output is correct
26	Correct	233 ms	39836 KB	Output is correct
27	Correct	172 ms	37452 KB	Output is correct
28	Correct	11 ms	10332 KB	Output is correct
29	Correct	191 ms	37560 KB	Output is correct
30	Correct	215 ms	36012 KB	Output is correct
31	Correct	204 ms	33108 KB	Output is correct
32	Correct	57 ms	17232 KB	Output is correct
33	Correct	256 ms	33880 KB	Output is correct