Submission #536644

#	Time	Username	Problem	Language	Result	Execution time	Memory
536644		rainboy	전압 (JOI14_voltage)	C11	100 / 100	131 ms	16340 KiB

voltage

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

#define N	100000
#define M	200000

int ij[M];
int *eh[N], eo[N];

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

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

char visited[N]; int dd[N], kk[N], k;

void dfs(int f, int i, int d) {
	int o;

	visited[i] = 1, dd[i] = d;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o];

		if (h != f) {
			int j = i ^ ij[h];

			if (!visited[j]) {
				dfs(h, j, d + 1);
				kk[i] += kk[j];
			} else if (dd[j] < dd[i]) {
				if ((dd[i] - dd[j]) % 2 == 0)
					kk[i]++, k++;
				else
					kk[i]--;
			} else {
				if ((dd[i] - dd[j]) % 2 == 0)
					kk[i]--;
				else
					kk[i]++;
			}
		}
	}
}

int main() {
	int n, m, h, i, j, cnt;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		ij[h] = i ^ j;
		append(i, h), append(j, h);
	}
	for (i = 0; i < n; i++)
		if (!visited[i])
			dfs(-1, i, 0);
	cnt = k == 1 ? 1 : 0;
	for (i = 0; i < n; i++)
		if (dd[i] > 0 && kk[i] == k)
			cnt++;
	printf("%d\n", cnt);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45