Submission #704726

#	Time	Username	Problem	Language	Result	Execution time	Memory
704726		rainboy	철도 요금 (JOI16_ho_t3)	C11	100 / 100	161 ms	15180 KiB

2016_ho_t3

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

#define N	100000
#define M	200000
#define Q	200000

int ii[M], jj[M];
int *ej[N], eo[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;
}

char visited[N]; int cnt;

void dfs(int i) {
	int o;

	if (visited[i])
		return;
	visited[i] = 1, cnt++;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs(j);
	}
}

int main() {
	static int dd[N], qu[N], hh[Q], ans[Q];
	static char incr[M];
	int n, m, q, g, h, i, j, d, o;

	scanf("%d%d%d", &n, &m, &q);
	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), i--, j--;
		ii[h] = i, jj[h] = j;
		append(i, j), append(j, i);
	}
	for (i = 0; i < n; i++)
		dd[i] = n;
	dd[0] = 0, qu[cnt++] = 0;
	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, qu[cnt++] = j;
		}
	}
	for (i = 0; i < n; i++)
		free(ej[i]);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
	for (g = 0; g < q; g++) {
		scanf("%d", &hh[g]), hh[g]--;
		incr[hh[g]] = 1;
	}
	for (h = 0; h < m; h++) {
		if (incr[h])
			continue;
		i = ii[h], j = jj[h];
		if (dd[i] + 1 == dd[j])
			append(i, j);
		else if (dd[j] + 1 == dd[i])
			append(j, i);
	}
	cnt = 0, dfs(0);
	for (g = q - 1; g >= 0; g--) {
		ans[g] = n - cnt;
		h = hh[g], i = ii[h], j = jj[h];
		if (dd[i] + 1 == dd[j]) {
			append(i, j);
			if (visited[i])
				dfs(j);
		} else if (dd[j] + 1 == dd[i]) {
			append(j, i);
			if (visited[j])
				dfs(i);
		}
	}
	for (g = 0; g < q; g++)
		printf("%d\n", ans[g]);
	return 0;
}

Compilation message (stderr)

2016_ho_t3.c: In function 'append':
2016_ho_t3.c:14:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
2016_ho_t3.c: In function 'main':
2016_ho_t3.c:39:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d%d%d", &n, &m, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.c:43:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.c:63:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%d", &hh[g]), hh[g]--;
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39