제출 #636603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
636603		rainboy	Jail (JOI22_jail)	C11	100 / 100	1032 ms	235816 KiB

jail

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

#define N	120000
#define M	N
#define L	17	/* L = ceil(log2(N)) */
#define N_	(M + N * L * 2)

int *ej[N], eo[N], *ej_[N_], eo_[N_], fo_[N_], n, m, 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 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, fo_[j]++;
}

int dd[N], pp[N][L];

void dfs1(int p, int i, int d) {
	int o, l;

	dd[i] = d;
	pp[i][0] = p;
	for (l = 1; l < L; l++)
		pp[i][l] = pp[i][l - 1] == -1 ? -1 : pp[pp[i][l - 1]][l - 1];
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs1(i, j, d + 1);
	}
}

int lca(int i, int j) {
	int tmp, l;

	if (dd[i] < dd[j])
		tmp = i, i = j, j = tmp;
	for (l = L - 1; l >= 0; l--)
		if (dd[i] - dd[j] >= 1 << l)
			i = pp[i][l];
	if (i == j)
		return i;
	for (l = L - 1; l >= 0; l--)
		if (dd[i] >= 1 << l && pp[i][l] != pp[j][l])
			i = pp[i][l], j = pp[j][l];
	return pp[i][0];
}

void dfs2(int i) {
	int o;

	if (fo_[i])
		return;
	fo_[i] = -1;
	for (o = eo_[i]; o--; ) {
		int j = ej_[i][o];

		fo_[j]--, dfs2(j);
	}
}

void add(int h, int i, int d, int t) {
	int l;

	for (l = L - 1; l >= 0; l--)
		if (dd[i] - d >= 1 << l) {
			if (t == 0)
				append_(m + (i * L + l << 1 | 0), h);
			else
				append_(h, m + (i * L + l << 1 | 1));
			i = pp[i][l];
		}
}

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		static int ii[M], jj[M], hhi[N], hhj[N];
		int h, i, j, l, a, yes;

		scanf("%d", &n);
		for (i = 0; i < n; i++)
			ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
		for (h = 0; h < n - 1; h++) {
			scanf("%d%d", &i, &j), i--, j--;
			append(i, j), append(j, i);
		}
		scanf("%d", &m);
		memset(hhi, -1, n * sizeof *hhi), memset(hhj, -1, n * sizeof *hhj);
		for (h = 0; h < m; h++) {
			scanf("%d%d", &i, &j), i--, j--;
			ii[h] = i, jj[h] = j;
			hhi[i] = hhj[j] = h;
		}
		dfs1(-1, 0, 0);
		n_ = m + n * L * 2;
		for (i = 0; i < n_; i++)
			ej_[i] = (int *) malloc(2 * sizeof *ej_[i]), eo_[i] = fo_[i] = 0;
		for (i = 0; i < n; i++) {
			if ((h = hhi[i]) != -1)
				append_(h, m + (i * L + 0 << 1 | 0));
			if ((h = hhj[i]) != -1)
				append_(m + (i * L + 0 << 1 | 1), h);
		}
		for (l = 0; l + 1 < L; l++)
			for (i = 0; i < n; i++) {
				append_(m + (i * L + l << 1 | 0), m + (i * L + l + 1 << 1 | 0));
				append_(m + (i * L + l + 1 << 1 | 1), m + (i * L + l << 1 | 1));
				if ((j = pp[i][l]) != -1) {
					append_(m + (j * L + l << 1 | 0), m + (i * L + l + 1 << 1 | 0));
					append_(m + (i * L + l + 1 << 1 | 1), m + (j * L + l << 1 | 1));
				}
			}
		for (h = 0; h < m; h++) {
			i = ii[h], j = jj[h], a = lca(i, j);
			if (dd[i] - dd[a] > 1)
				add(h, pp[i][0], dd[a], 0);
			if (i != a)
				add(h, i, dd[a], 1);
			if (j != a)
				add(h, j, dd[a], 0);
			if (dd[j] - dd[a] > 1)
				add(h, pp[j][0], dd[a], 1);
			if (a != i)
				append_(m + (a * L + 0 << 1 | 0), h);
			if (a != j)
				append_(h, m + (a * L + 0 << 1 | 1));
		}
		for (i = 0; i < n_; i++)
			dfs2(i);
		yes = 1;
		for (i = 0; i < n_; i++)
			if (fo_[i] > 0) {
				yes = 0;
				break;
			}
		printf(yes ? "Yes\n" : "No\n");
		for (i = 0; i < n; i++)
			free(ej[i]);
		for (i = 0; i < n_; i++)
			free(ej_[i]);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

jail.c: In function 'append':
jail.c:15:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   15 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
jail.c: In function 'append_':
jail.c:23:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   23 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
jail.c: In function 'add':
jail.c:80:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   80 |     append_(m + (i * L + l << 1 | 0), h);
      |                  ~~~~~~^~~
jail.c:82:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   82 |     append_(h, m + (i * L + l << 1 | 1));
      |                     ~~~~~~^~~
jail.c: In function 'main':
jail.c:115:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  115 |     append_(h, m + (i * L + 0 << 1 | 0));
      |                     ~~~~~~^~~
jail.c:117:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  117 |     append_(m + (i * L + 0 << 1 | 1), h);
      |                  ~~~~~~^~~
jail.c:121:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  121 |     append_(m + (i * L + l << 1 | 0), m + (i * L + l + 1 << 1 | 0));
      |                  ~~~~~~^~~
jail.c:121:54: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  121 |     append_(m + (i * L + l << 1 | 0), m + (i * L + l + 1 << 1 | 0));
      |                                            ~~~~~~~~~~^~~
jail.c:122:28: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  122 |     append_(m + (i * L + l + 1 << 1 | 1), m + (i * L + l << 1 | 1));
      |                  ~~~~~~~~~~^~~
jail.c:122:54: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  122 |     append_(m + (i * L + l + 1 << 1 | 1), m + (i * L + l << 1 | 1));
      |                                                ~~~~~~^~~
jail.c:124:25: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  124 |      append_(m + (j * L + l << 1 | 0), m + (i * L + l + 1 << 1 | 0));
      |                   ~~~~~~^~~
jail.c:124:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  124 |      append_(m + (j * L + l << 1 | 0), m + (i * L + l + 1 << 1 | 0));
      |                                             ~~~~~~~~~~^~~
jail.c:125:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  125 |      append_(m + (i * L + l + 1 << 1 | 1), m + (j * L + l << 1 | 1));
      |                   ~~~~~~~~~~^~~
jail.c:125:55: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  125 |      append_(m + (i * L + l + 1 << 1 | 1), m + (j * L + l << 1 | 1));
      |                                                 ~~~~~~^~~
jail.c:139:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  139 |     append_(m + (a * L + 0 << 1 | 0), h);
      |                  ~~~~~~^~~
jail.c:141:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  141 |     append_(h, m + (a * L + 0 << 1 | 1));
      |                     ~~~~~~^~~
jail.c:90:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
jail.c:95:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |   scanf("%d", &n);
      |   ^~~~~~~~~~~~~~~
jail.c:99:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |    scanf("%d%d", &i, &j), i--, j--;
      |    ^~~~~~~~~~~~~~~~~~~~~
jail.c:102:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |   scanf("%d", &m);
      |   ^~~~~~~~~~~~~~~
jail.c:105:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |    scanf("%d%d", &i, &j), i--, j--;
      |    ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23