oj.uz

답안 #872822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872822 2023-11-13T21:37:25 Z rainboy Rigged Roads (NOI19_riggedroads) C
100 / 100
 256 ms 45140 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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