Submission #70526137

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
int ec[512345], *es[512345];
void ae(int f, int t) {
  es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
  if (es[f] == NULL) exit(2);
  es[f][ec[f]++] = t;
}
int cmp(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return (a > b) - (a < b);
}
int find(const int* arr, int size, int target) {
  int l = 0, r = size - 1;
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (arr[m] == target) return m;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int ec[512345], *es[512345];

void ae(int f, int t) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = t;
}

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (a > b) - (a < b);
}

int find(const int* arr, int size, int target) {
	int l = 0, r = size - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (arr[m] == target) return m;
		else if (arr[m] < target) l = m + 1;
		else r = m - 1;
	}
	return size;
}

struct res_s {
	int vert, depth;
};

struct res_s* memo[512345];
char* memo_valid[512345];

struct res_info_s {
	int vert;
	struct res_s res;
};

int cmp_info(const void* x, const void* y) {
	struct res_info_s a = *(const struct res_info_s*)x, b = *(const struct res_info_s*)y;
	if (a.res.depth != b.res.depth) {
		return (a.res.depth < b.res.depth) - (a.res.depth > b.res.depth);
	}
	return (a.res.vert < b.res.vert) - (a.res.vert > b.res.vert);
}

struct res_info_s* info[512345];
int info_status[512345]; /* 0：未調査 1～N：そこのみ未調査 -1：調査済 */

struct res_s solve(int vert, int from) {
	struct res_s ans;
	int from_id = find(es[vert], ec[vert], from);
	if (memo_valid[vert][from_id]) return memo[vert][from_id];

	if (info_status[vert] == 0) {
		/* フル調査 */
		int i;
		info[vert] = malloc(sizeof(*info[vert]) * ec[vert]);
		info_status[vert] = -1;
		for (i = 0; i < ec[vert]; i++) {
			info[vert][i].vert = es[vert][i];
			if (es[vert][i] != from) {
				info[vert][i].res = solve(es[vert][i], vert);
			} else {
				info[vert][i].res = (struct res_s){ vert, 0 };
				info_status[vert] = es[vert][i];
			}
		}
		qsort(info[vert], ec[vert], sizeof(*info[vert]), cmp_info);
	} else if (info_status[vert] > 0) {
		/* 足りないところだけ調査 */
		int i;
		for (i = 0; i < ec[vert]; i++) {
			if (info[vert][i].vert == info_status[vert]) {
				info[vert][i].res = solve(info[vert][i].vert, vert);
			}
		}
		info_status[vert] = -1;
		qsort(info[vert], ec[vert], sizeof(*info[vert]), cmp_info);
	}

	if (info[vert][0].vert != from) {
		ans.vert = info[vert][0].res.vert;
		ans.depth = info[vert][0].res.depth + 1;
	} else if (ec[vert] > 1 && info[vert][1].vert != from) {
		ans.vert = info[vert][1].res.vert;
		ans.depth = info[vert][1].res.depth + 1;
	} else {
		ans.vert = vert;
		ans.depth = 0;
	}
	memo[vert][from_id] = ans;
	memo_valid[vert][from_id] = 1;
	return ans;
}

int main(void) {
	int N, i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i < N; i++) {
		int A, B;
		if (scanf("%d%d", &A, &B) != 2) return 1;
		ae(A, B);
		ae(B, A);
	}
	for (i = 1; i <= N; i++) {
		if (ec[i] > 0) qsort(es[i], ec[i], sizeof(*es[i]), cmp);
		memo[i] = malloc(sizeof(*memo[i]) * (ec[i] + 1));
		memo_valid[i] = calloc(ec[i] + 1, sizeof(*memo_valid[i]));
	}
	for (i = 1; i <= N; i++) {
		struct res_s ans = solve(i, 0);
		printf("%d\n", ans.vert);
	}
	return 0;
}

Submission Info

Judge Result