Submission #67455415

Source Code Expand

Copy
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>
int cmp(const void* x, const void* y) {
  int a = *(const int*)x, b = *(const int*)y;
  return a < b ? -1 : a > b;
}
int N;
int pA[114514], qA[114514];
int M;
int pB[114514], qB[114514];
struct fs_s {
  int first, second;
};
struct depth_s {
  int target;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <inttypes.h>

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

int N;
int pA[114514], qA[114514];
int M;
int pB[114514], qB[114514];

struct fs_s {
	int first, second;
};

struct depth_s {
	int target;
	int depth;
};

/* depth の降順 */
int cmp_depth(const void* x, const void* y) {
	struct depth_s a = *(const struct depth_s*)x, b = *(const struct depth_s*)y;
	return a.depth > b.depth ? -1 : a.depth < b.depth;
}

struct ki_s {
	int nnode;
	int ec[114514], *es[114514];
	struct fs_s* memos[114514]; /* その頂点を根としたとき、深さベスト2 (→直径用) */
	struct depth_s* depths[114514]; /* その頂点から各辺を行ったときの深さ (内部情報) */
	int node_depth[114514]; /* その頂点を根としたときの深さ (あとの処理用) */
	int chokkei;
};

struct ki_s A, B;

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

/* node から from 以外に向かう際の深さを求めて返す */
int get_depth(struct ki_s* ki, int node, int from) {
	/* from に対応するメモ配列の要素を求める */
	int key = ki->ec[node];
	int l = 0, r = ki->ec[node] - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (ki->es[node][m] == from) {
			key = m;
			break;
		} else if (ki->es[node][m] < from) {
			l = m + 1;
		} else {
			r = m - 1;
		}
	}
	/* 計算済みであれば、その結果を返す */
	if (ki->memos[node][key].first >= 0) {
		return ki->memos[node][key].first;
	}
	/* 状況に応じて、繋がっているノードの深さの計算を行う */
	if (ki->depths[node] == NULL) {
		/* 未計算なら、フルで計算を行う (来たノードがあれば、除く) */
		int i;
		ki->depths[node] = malloc(sizeof(*ki->depths[node]) * (ki->ec[node] + 2)); /* 番兵？用に要素を確保 */
		if (ki->depths[node] == NULL) exit(2);
		ki->depths[node][ki->ec[node]] = (struct depth_s){ -1, -1 };
		ki->depths[node][ki->ec[node] + 1] = (struct depth_s){ -1, -1 };
		for (i = 0; i < ki->ec[node]; i++) {
			ki->depths[node][i].target = ki->es[node][i];
			if (ki->es[node][i] == from) {
				ki->depths[node][i].depth = -1;
			} else {
				ki->depths[node][i].depth = get_depth(ki, ki->es[node][i], node);
			}
		}
		qsort(ki->depths[node], ki->ec[node], sizeof(*ki->depths[node]), cmp_depth);
	} else if (ki->depths[node][ki->ec[node] - 1].target != from && ki->depths[node][ki->ec[node] - 1].depth < 0) {
		/* あと1個計算してなくて、計算できるなら、それの計算を行う */
		ki->depths[node][ki->ec[node] - 1].depth = get_depth(ki, ki->depths[node][ki->ec[node] - 1].target, node);
		qsort(ki->depths[node], ki->ec[node], sizeof(*ki->depths[node]), cmp_depth);
	}
	/* 計算結果と、来たノードによって、深さベスト2を求める */
	if (ki->depths[node][0].target == from) {
		ki->memos[node][key] = (struct fs_s){ ki->depths[node][1].depth + 1, ki->depths[node][2].depth + 1 };
	} else if (ki->depths[node][1].target == from) {
		ki->memos[node][key] = (struct fs_s){ ki->depths[node][0].depth + 1, ki->depths[node][2].depth + 1 };
	} else {
		ki->memos[node][key] = (struct fs_s){ ki->depths[node][0].depth + 1, ki->depths[node][1].depth + 1 };
	}
	return ki->memos[node][key].first;
}

/* ki が指すデータはゼロクリア (グローバル変数なので) されていることを前提としている */
void ki_init(struct ki_s* ki) {
	int i;
	/* 辺リストをソートし、メモ配列を確保する */
	for (i = 1; i <= ki->nnode; i++) {
		qsort(ki->es[i], ki->ec[i], sizeof(*ki->es[i]), cmp);
		ki->memos[i] = malloc(sizeof(*ki->memos[i]) * (ki->ec[i] + 1));
		if (ki->memos[i] == NULL) exit(2);
		memset(ki->memos[i], -1, sizeof(*ki->memos[i]) * (ki->ec[i] + 1));
	}
	/* 頂点の調査を行い、深さと直径を求める */
	for (i = 1; i <= ki->nnode; i++) {
		int candidate;
		ki->node_depth[i] = get_depth(ki, i, 0);
		candidate = ki->memos[i][ki->ec[i]].first + ki->memos[i][ki->ec[i]].second;
		if (candidate > ki->chokkei) ki->chokkei = candidate;
	}
}

int B_depths[114514];
int64_t B_depths_sum[114514];

int main(void) {
	int i;
	int min_value;
	int64_t ans = 0;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N - 1; i++) {
		if (scanf("%d%d", &pA[i], &qA[i]) != 2) return 1;
		ae(&A, pA[i], qA[i]);
		ae(&A, qA[i], pA[i]);
	}
	if (scanf("%d", &M) != 1) return 1;
	for (i = 0; i < M - 1; i++) {
		if (scanf("%d%d", &pB[i], &qB[i]) != 2) return 1;
		ae(&B, pB[i], qB[i]);
		ae(&B, qB[i], pB[i]);
	}
	A.nnode = N;
	B.nnode = M;
	ki_init(&A);
	ki_init(&B);

	memcpy(B_depths + 1, B.node_depth + 1, sizeof(*B.node_depth) * B.nnode);
	qsort(B_depths + 1, B.nnode, sizeof(*B_depths), cmp);
	for (i = 1; i <= B.nnode; i++) {
		B_depths_sum[i] = B_depths_sum[i - 1] + B_depths[i];
	}
	min_value = A.chokkei >= B.chokkei ? A.chokkei : B.chokkei;

	for (i = 1; i <= A.nnode; i++) {
		int threshold = min_value - A.node_depth[i] - 1;
		int le = 0, g = B.nnode + 1;
		while (le + 1 < g) {
			int m = le + (g - le) / 2;
			if (B_depths[m] <= threshold) le = m; else g = m;
		}
		ans += (int64_t)min_value * le;
		ans += B_depths_sum[B.nnode] - B_depths_sum[le];
		ans += (int64_t)(A.node_depth[i] + 1) * (B.nnode - le);
	}

	printf("%" PRId64 "\n", ans);
	return 0;
}

/*

ポイント：2頂点以上の木 → 辺が出ていない頂点は無い

それぞれの木で、各頂点を根としたときの深さを求める
また、それぞれの木の直径も求めておく

Aの各頂点について、Bの各頂点と結んだときの直径を、求めておいた深さを使って求める
ただし、それがもとの木の直径のmax未満の場合、もとの木の直径のmaxが新しい木の直径

*/

Submission Info

Submission Time
Task B - Bonsai Grafting
User mikecat
Language C (gcc 12.2.0)
Score 700
Code Size 6097 Byte
Status AC
Exec Time 127 ms
Memory 38216 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 2
AC × 42
Set Name Test Cases
Sample 01.txt, 02.txt
All 01.txt, 02.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt
Case Name Status Exec Time Memory
01.txt AC 0 ms 1696 KiB
02.txt AC 0 ms 1804 KiB
11.txt AC 0 ms 1816 KiB
12.txt AC 0 ms 1700 KiB
13.txt AC 0 ms 1660 KiB
14.txt AC 0 ms 1776 KiB
15.txt AC 1 ms 1716 KiB
16.txt AC 0 ms 1772 KiB
17.txt AC 0 ms 1660 KiB
18.txt AC 0 ms 1652 KiB
19.txt AC 0 ms 1780 KiB
20.txt AC 0 ms 1648 KiB
21.txt AC 119 ms 32612 KiB
22.txt AC 125 ms 33240 KiB
23.txt AC 118 ms 32708 KiB
24.txt AC 125 ms 37092 KiB
25.txt AC 125 ms 33592 KiB
26.txt AC 123 ms 33276 KiB
27.txt AC 125 ms 37536 KiB
28.txt AC 120 ms 32560 KiB
29.txt AC 123 ms 37028 KiB
30.txt AC 125 ms 37972 KiB
31.txt AC 119 ms 32564 KiB
32.txt AC 124 ms 33108 KiB
33.txt AC 119 ms 32696 KiB
34.txt AC 122 ms 38216 KiB
35.txt AC 127 ms 33580 KiB
36.txt AC 121 ms 33120 KiB
37.txt AC 127 ms 36252 KiB
38.txt AC 117 ms 32684 KiB
39.txt AC 122 ms 36452 KiB
40.txt AC 120 ms 36832 KiB
41.txt AC 60 ms 17828 KiB
42.txt AC 55 ms 16696 KiB
43.txt AC 65 ms 17680 KiB
44.txt AC 53 ms 16600 KiB
45.txt AC 66 ms 18408 KiB
46.txt AC 62 ms 17152 KiB
47.txt AC 68 ms 23108 KiB
48.txt AC 53 ms 16684 KiB
49.txt AC 64 ms 20848 KiB
50.txt AC 55 ms 19588 KiB
Facebook Twitter Telegram Share

2025-07-09 (Wed)
23:20:46 +09:00

More…