結果

問題 No.1833 Subway Planning
コンテスト
ユーザー 👑 ygussany
提出日時 2022-01-09 12:33:03
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 499 ms / 4,000 ms
コード長 4,701 bytes
コンパイル時間 514 ms
コンパイル使用メモリ 35,200 KB
実行使用メモリ 44,028 KB
最終ジャッジ日時 2024-11-14 10:20:32
合計ジャッジ時間 6,825 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

typedef struct Edge {
	struct Edge *next;
	int v, cost;
} edge;

typedef struct {
	int key, id;
} data;

typedef struct {
	data obj[200001];
	int size;
} max_heap;

void push(max_heap* h, data x)
{
	int i = ++(h->size), j = i >> 1;
	data tmp;
	h->obj[i] = x;
	while (j > 0) {
		if (h->obj[i].key > h->obj[j].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j >>= 1;
		} else break;
	}
}

data pop(max_heap* h)
{
	int i = 1, j = 2;
	data output = h->obj[1], tmp;
	h->obj[1] = h->obj[(h->size)--];
	while (j <= h->size) {
		if (j < h->size && h->obj[j^1].key > h->obj[j].key) j ^= 1;
		if (h->obj[j].key > h->obj[i].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
			j <<= 1;
		} else break;
	}
	return output;
}

void chmin(int* a, int b)
{
	if (*a > b) *a = b;
}

void chmax(int* a, int b)
{
	if (*a < b) *a = b;
}

int main()
{
	int i, N, u, w, c;
	edge *adj[200001] = {}, e[400001], *p;
	scanf("%d", &N);
	for (i = 0; i < N - 1; i++) {
		scanf("%d %d %d", &u, &w, &c);
		e[i*2].v = w;
		e[i*2+1].v = u;
		e[i*2].cost = c;
		e[i*2+1].cost = c;
		e[i*2].next = adj[u];
		e[i*2+1].next = adj[w];
		adj[u] = &(e[i*2]);
		adj[w] = &(e[i*2+1]);
	}
	
	int x, par[20][200001][2] = {}, depth[200001] = {}, q[200001], head, tail;
	data d;
	max_heap h;
	h.size = 0;
	depth[0] = 0;
	depth[1] = 1;
	q[0] = 1;
	for (head = 0, tail = 1; head < tail; head++) {
		u = q[head];
		for (p = adj[u]; p != NULL; p = p->next) {
			w = p->v;
			if (depth[w] == 0) {
				par[0][w][0] = u;
				par[0][w][1] = p->cost;
				depth[w] = depth[u] + 1;
				for (i = 0, x = u; par[i][x][0] != 0; x = par[i++][x][0]) {
					fflush(stdout);
					par[i+1][w][0] = par[i][x][0];
					par[i+1][w][1] = par[i][w][1];
					chmin(&(par[i+1][w][1]), par[i][x][1]);
				}
				d.key = p->cost;
				d.id = w;
				push(&h, d);
				q[tail++] = w;
			}
		}
	}
	
	int k, ans = h.obj[1].key, s, t, lca, flag = 0, max = h.obj[1].key, min, tmp;
	while (h.size > 0) {
		k = h.obj[1].key;
		while (h.size > 0 && h.obj[1].key == k) {
			d = pop(&h);
			if (flag == 0) {
				s = d.id;
				t = par[0][s][0];
				flag = 1;
				min = d.key;
			} else if (flag == 1) {
				u = s;
				w = d.id;
				tmp = 1 << 30;
				while (depth[u] > depth[w]) {
					for (i = 0; depth[par[i][u][0]] >= depth[w]; i++);
					chmin(&tmp, par[i-1][u][1]);
					u = par[i-1][u][0];
				}
				while (depth[u] < depth[w]) {
					for (i = 0; depth[par[i][w][0]] >= depth[u]; i++);
					chmin(&tmp, par[i-1][w][1]);
					w = par[i-1][w][0];
				}
				while (u != w) {
					for (i = 1; par[i][u][0] != par[i][w][0]; i++);
					chmin(&tmp, par[i-1][u][1]);
					chmin(&tmp, par[i-1][w][1]);
					u = par[i-1][u][0];
					w = par[i-1][w][0];
				}
				if (u == s) {
					s = d.id;
					chmin(&min, tmp);
				} else if (u == d.id) {
					t = par[0][d.id][0];
					chmin(&min, tmp);
					chmin(&min, d.key);
				} else if (depth[u] <= depth[t]) {
					flag = 2;
					lca = u;
					t = d.id;
					chmin(&min, tmp);
				} else {
					flag = -1;
					break;
				}
			} else {
				u = s;
				w = d.id;
				tmp = 1 << 30;
				while (depth[u] > depth[w]) {
					for (i = 0; depth[par[i][u][0]] >= depth[w]; i++);
					chmin(&tmp, par[i-1][u][1]);
					u = par[i-1][u][0];
				}
				while (depth[u] < depth[w]) {
					for (i = 0; depth[par[i][w][0]] >= depth[u]; i++);
					chmin(&tmp, par[i-1][w][1]);
					w = par[i-1][w][0];
				}
				while (u != w) {
					for (i = 1; par[i][u][0] != par[i][w][0]; i++);
					chmin(&tmp, par[i-1][u][1]);
					chmin(&tmp, par[i-1][w][1]);
					u = par[i-1][u][0];
					w = par[i-1][w][0];
				}
				if (u == s) {
					s = d.id;
					chmin(&min, tmp);
					continue;
				} else if (u != d.id || depth[u] <= depth[lca]) flag = -1;

				u = t;
				w = d.id;
				tmp = 1 << 30;
				while (depth[u] > depth[w]) {
					for (i = 0; depth[par[i][u][0]] >= depth[w]; i++);
					chmin(&tmp, par[i-1][u][1]);
					u = par[i-1][u][0];
				}
				while (depth[u] < depth[w]) {
					for (i = 0; depth[par[i][w][0]] >= depth[u]; i++);
					chmin(&tmp, par[i-1][w][1]);
					w = par[i-1][w][0];
				}
				while (u != w) {
					for (i = 1; par[i][u][0] != par[i][w][0]; i++);
					chmin(&tmp, par[i-1][u][1]);
					chmin(&tmp, par[i-1][w][1]);
					u = par[i-1][u][0];
					w = par[i-1][w][0];
				}
				if (u == t) {
					flag = 2;
					t = d.id;
					chmin(&min, tmp);
					continue;
				} else if (u == d.id && depth[d.id] > depth[lca]) flag = 2;
				if (flag < 0) break;
			}
		}
		if (flag >= 0) {
			if (ans > max - min) {
				ans = max - min;
				if (h.size > 0) chmax(&ans, h.obj[1].key);
			} else break;
		} else break;
	}
	printf("%d\n", ans);
	fflush(stdout);
	return 0;
}
0