Submission #745245

#	Time	Username	Problem	Language	Result	Execution time	Memory
745245		rainboy	Hotspot (NOI17_hotspot)	C11	100 / 100	652 ms	1108 KiB

hotspot

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

#define N	5000
#define M	40000
#define K	2000

int *ej[N], eo[N], n;

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

void bfs(int *dd, int *kk, int s) {
	static int qu[N];
	int cnt, h, i, j, d, o;

	for (i = 0; i < n; i++)
		dd[i] = n;
	cnt = 0;
	dd[s] = 0, kk[s] = 1, qu[cnt++] = s;
	for (h = 0; h < cnt; h++) {
		i = qu[h], d = dd[i] + 1;
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (dd[j] > d)
				dd[j] = d, kk[j] = kk[i], qu[cnt++] = j;
			else if (dd[j] == d)
				kk[j] += kk[i];
		}
	}
}

double xx[N];

void solve(int s, int t) {
	static int dds[N], kks[N], ddt[N], kkt[N];
	int i;

	bfs(dds, kks, s), bfs(ddt, kkt, t);
	for (i = 0; i < n; i++)
		if (dds[i] + ddt[i] == dds[t])
			xx[i] += (double) kks[i] * kkt[i] / kks[t];
}

int main() {
	int m, k, h, i, i_, j, s, t;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j);
		append(i, j), append(j, i);
	}
	scanf("%d", &k);
	while (k--) {
		scanf("%d%d", &s, &t);
		solve(s, t);
	}
	i_ = -1;
	for (i = 0; i < n; i++)
		if (i_ == -1 || xx[i_] < xx[i])
			i_ = i;
	printf("%d\n", i_);
	return 0;
}

Compilation message (stderr)

hotspot.c: In function 'append':
hotspot.c:13:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   13 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
hotspot.c: In function 'main':
hotspot.c:53:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
hotspot.c:57:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d%d", &i, &j);
      |   ^~~~~~~~~~~~~~~~~~~~~
hotspot.c:60:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%d", &k);
      |  ^~~~~~~~~~~~~~~
hotspot.c:62:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d%d", &s, &t);
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 18 / 18
• Subtask 5: 26 / 26
• Subtask 6: 36 / 36