Submission #62323815

---

Source Code Expand

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

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

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;
}

struct q_s {
	int node;
	int64_t cost;
};

int q_cap = 0, q_size = 0;
struct q_s* q;

void qadjust(int pos) {
	for (;;) {
		int i;
		int minpos = pos;
		for (i = 1; i <= 2; i++) {
			int c = pos * 2 + i;
			if (c < q_size && q[c].cost < q[minpos].cost) minpos = c;
		}
		if (minpos == pos) {
			if (pos == 0) return;
			pos = (pos - 1) / 2;
		} else {
			struct q_s temp = q[pos];
			q[pos] = q[minpos];
			q[minpos] = temp;
			pos = minpos;
		}
	}
}

void qadd(int node, int64_t cost) {
	if (q_size >= q_cap) {
		q = realloc(q, sizeof(*q) * (q_size + 1));
		if (q == NULL) exit(2);
		q_cap = q_size + 1;
	}
	q[q_size].node = node;
	q[q_size].cost = cost;
	q_size++;
	qadjust(q_size - 1);
}

struct q_s qget(void) {
	struct q_s ret;
	if (q_size <= 0) exit(42);
	ret = q[0];
	q_size--;
	if (q_size > 0) {
		q[0] = q[q_size - 1];
		qadjust(0);
	}
	return ret;
}

int N, M;
int A[212345];
int U[212345], V[212345];

int64_t node_cost[212345];
char deleted[212345];

int main(void) {
	int i, j;
	int64_t ans = 0;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	for (i = 0; i < M; i++) {
		if (scanf("%d%d", &U[i], &V[i]) != 2) return 1;
		ae(U[i], V[i]);
		ae(V[i], U[i]);
	}
	for (i = 1; i <= N; i++) {
		for (j = 0; j < ec[i]; j++) {
			node_cost[i] += A[es[i][j]];
		}
		qadd(i, node_cost[i]);
	}
	while (q_size > 0) {
		struct q_s cur = qget();
		if (!deleted[cur.node]) {
			deleted[cur.node] = 1;
			if (ans < cur.cost) ans = cur.cost;
			for (i = 0; i < ec[cur.node]; i++) {
				int node = es[cur.node][i];
				if (!deleted[node]) {
					node_cost[node] -= A[cur.node];
					qadd(node, node_cost[node]);
				}
			}
		}
	}
	printf("%" PRId64 "\n", ans);
	return 0;
}

/*

全体のコストは、和ではなく最大値である
どれかの頂点を選んで操作を行わないと、先に進めない
操作により、続く操作にかかるコストが上がることはない

→ 今の状態をみて、かかるコストが最小の頂点を選んで操作すれば良い
→ プライオリティーキュー

*/

Submission Info

Judge Result