Submission #544606

#	Time	Username	Problem	Language	Result	Execution time	Memory
544606		rainboy	Pipes (BOI13_pipes)	C11	100 / 100	68 ms	10036 KiB

pipes

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

#define N	100000

int *oh[N], oo[N];

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

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

int ij[N]; long long cc[N]; char used[N];
long long aa[N]; int hh[N], dd[N];

void dfs(int i) {
	if (dd[i] == 1) {
		int h, j;

		h = hh[i], j = i ^ ij[hh[i]];
		cc[h] = aa[i] * 2, used[h] = 1;
		aa[j] -= aa[i];
		hh[i] ^= h, dd[i]--;
		hh[j] ^= h, dd[j]--;
		dfs(j);
	}
}

int main() {
	static int qu[N], qu_[N];
	int n, m, g, h, h_, i, i_, j, cnt;

	scanf("%d%d", &n, &m);
	if (m > n) {
		printf("0\n");
		return 0;
	}
	for (i = 0; i < n; i++)
		oh[i] = (int *) malloc(2 * sizeof *oh[i]);
	for (i = 0; i < n; i++)
		scanf("%lld", &aa[i]);
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		ij[h] = i ^ j;
		append(i, h), append(j, h);
		hh[i] ^= h, hh[j] ^= h;
	}
	for (i = 0; i < n; i++)
		dd[i] = oo[i];
	for (i = 0; i < n; i++)
		dfs(i);
	if (m == n) {
		i = 0;
		while (dd[i] == 0)
			i++;
		i_ = i, h_ = -1, cnt = 0;
		do {
			int o;

			qu[cnt] = i_;
			for (o = 0; o < oo[i_]; o++) {
				h = oh[i_][o];
				if (h != h_ && !used[h]) {
					qu_[cnt] = h_ = h;
					i_ ^= ij[h];
					break;
				}
			}
			cnt++;
		} while (i_ != i);
		h = qu_[cnt - 1];
		for (g = 0; g < cnt; g++) {
			i = qu[g];
			cc[h] += (g % 2 == 0 ? 1 : -1) * aa[i];
		}
		for (g = 0; g < cnt - 1; g++) {
			i = qu[g], h = qu_[(g - 1 + cnt) % cnt], h_ = qu_[g];
			cc[h_] = aa[i] * 2 - cc[h];
		}
		if (cnt % 2 == 0) {
			printf("0\n");
			return 0;
		}
	}
	for (h = 0; h < m; h++)
		printf("%lld\n", cc[h]);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70