Submission #544723

#	Time	Username	Problem	Language	Result	Execution time	Memory
544723		rainboy	Tug of War (BOI15_tug)	C11	100 / 100	306 ms	6372 KiB

tug

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

#define N	30000
#define N_	(N * 2)
#define W	20
#define S	(N * W)

int ii[N_], jj[N_], ww[N_];
int *eh[N_], eo[N_];

void link(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_], visited_[N_]; int qu1[N_], qu2[N_], cnt, cnt_;

void dfs1(int i) {
	int o;

	if (visited[i])
		return;
	visited[i] = 1, qu1[cnt++] = i;
	for (o = 0; o < eo[i]; o++) {
		int h = eh[i][o];

		if (!visited_[h]) {
			int j = i ^ ii[h] ^ jj[h];

			visited_[h] = 1, qu2[cnt_++] = h;
			dfs1(j);
		}
	}
}

int main() {
	static int ae[N_], dd[N_], qu_[N_], kk[S + 1], dq[S + 1];
	static char used[N_], dp[S + 1];
	int n, d_, h, h_, i, j, d, w, s;

	scanf("%d%d", &n, &d_);
	for (i = 0; i < n * 2; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < n * 2; h++) {
		scanf("%d%d%d", &i, &j, &w), i--, j--, j += n;
		ae[i] ^= h, dd[i]++;
		ae[j] ^= h, dd[j]++;
		ii[h] = i, jj[h] = j, ww[h] = w;
		link(i, h), link(j, h);
	}
	d = 0;
	for (i = 0; i < n * 2; i++)
		if (!visited[i]) {
			cnt = 0, cnt_ = 0;
			dfs1(i);
			if (cnt != cnt_) {
				printf("NO\n");
				return 0;
			}
			for (h = 0; h < cnt; h++)
				dd[qu1[h]] = eo[qu1[h]];
			cnt_ = 0;
			for (h = 0; h < cnt; h++)
				if (dd[qu1[h]] == 1)
					qu_[cnt_++] = qu1[h];
			while (cnt_) {
				i = qu_[--cnt_], h = ae[i], j = i ^ ii[h] ^ jj[h];
				used[h] = 1, d += i < n ? ww[h] : -ww[h];
				ae[i] ^= h, dd[i]--;
				ae[j] ^= h, dd[j]--;
				if (dd[j] == 1)
					qu_[cnt_++] = j;
			}
			for (h = 0; h < cnt; h++)
				if (!used[qu2[h]]) {
					h_ = qu2[h], i = ii[h_];
					break;
				}
			j = i;
			w = 0;
			do {
				h_ = ae[j] ^ h_;
				w += j < n ? ww[h_] : -ww[h_];
				j ^= ii[h_] ^ jj[h_];
			} while (j != i);
			if (w < 0)
				w = -w;
			d += w;
			kk[w]++;
		}
	dp[0] = 1;
	for (w = 0; w <= S; w++)
		if (kk[w] > 0) {
			int k = kk[w];

			for (s = 0; s <= S && s * 2 <= d + d_; s++)
				if (dp[s])
					dq[s] = 0;
				else if ((dq[s] = (s < w ? k : dq[s - w]) + 1) <= k)
					dp[s] = 1;
		}
	for (s = 0; s <= S && s * 2 <= d + d_; s++)
		if (dp[s] && d - s * 2 <= d_) {
			printf("YES\n");
			return 0;
		}
	printf("NO\n");
	return 0;
}

Compilation message (stderr)

tug.c: In function 'link':
tug.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
tug.c: In function 'main':
tug.c:46:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d%d", &n, &d_);
      |  ^~~~~~~~~~~~~~~~~~~~~~
tug.c:50:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%d%d%d", &i, &j, &w), i--, j--, j += n;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
tug.c:87:8: warning: 'h_' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |     h_ = ae[j] ^ h_;
      |     ~~~^~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 23 / 23
• Subtask 4: 29 / 29