oj.uz

답안 #706515

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
706515 2023-03-06T20:53:38 Z rainboy Unique Cities (JOI19_ho_t5) C
32 / 100
 1073 ms 39664 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N)) */

int max(int a, int b) { return a > b ? a : b; }

int *ej[N], eo[N], aa[N], pp[N], ans[N], 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;
}

int d_, i_;

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

	pp[i] = p;
	if (d_ < d)
		d_ = d, i_ = i;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

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

char path[N]; int dd[N];

void dfs2(int p, int i) {
	int o;

	dd[i] = 0;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p && !path[j]) {
			dfs2(i, j);
			dd[i] = max(dd[i], dd[j] + 1);
		}
	}
}

int mn[N_ * 2], kk[N_ * 2], lz[N_], h_, n_;

void put(int i, int x) {
	mn[i] += x;
	if (i < n_)
		lz[i] += x;
}

void pus(int i) {
	if (lz[i])
		put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = 0;
}

void pul(int i) {
	if (!lz[i]) {
		int l = i << 1, r = l | 1;

		if (mn[l] < mn[r])
			mn[i] = mn[l], kk[i] = kk[l];
		else if (mn[l] > mn[r])
			mn[i] = mn[r], kk[i] = kk[r];
		else
			mn[i] = mn[l], kk[i] = kk[l] + kk[r];
	}
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void build(int n) {
	h_ = 0;
	while (1 << h_ <= n)
		h_++;
	n_ = 1 << h_;
	memset(mn, 0, n_ * 2 * sizeof *mn);
	memset(kk, 0, n_ * 2 * sizeof *kk);
	memset(lz, 0, n_ * sizeof *lz);
}

void update(int l, int r, int x) {
	int l_, r_;

	if (l > r)
		return;
	l_ = l += n_, r_ = r += n_;
	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, x);
		if ((r & 1) == 0)
			put(r--, x);
	}
	pull(l_), pull(r_);
}

void upd(int i, int x) {
	kk[i += n_] += x, pull(i);
}

int gg[N], cnt;

void dfs3(int p, int i) {
	int o, g, unique;

	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p && !path[j])
			update(cnt - 1 - dd[j], cnt - 1, 1);
	}
	ans[i] = kk[1];
	g = gg[aa[i]], unique = 1;
	if (g >= 0) {
		push(n_ + g);
		if (mn[n_ + g] == 0)
			unique = 0;
	}
	if (unique)
		gg[aa[i]] = cnt, upd(cnt, 1);
	cnt++;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p && !path[j]) {
			update(cnt - 2 - dd[j], cnt - 2, -1);
			dfs3(i, j);
			update(cnt - 2 - dd[j], cnt - 2, 1);
		}
	}
	cnt--;
	if (unique)
		gg[aa[i]] = g, upd(cnt, -1);
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p && !path[j])
			update(cnt - 1 - dd[j], cnt - 1, -1);
	}
}

int main() {
	static int ii[N];
	int n, m, g, h, i, j, u, v, o, unique;

	scanf("%d%*d", &n);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
	}
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]), aa[i]--;
	d_ = -1, i_ = -1, dfs1(-1, 0, 0);
	u = i_;
	d_ = -1, i_ = -1, dfs1(-1, u, 0);
	v = i_;
	m = 0;
	while (v != u)
		ii[m++] = v, v = pp[v];
	ii[m++] = u;
	for (h = 0; h < m; h++)
		path[ii[h]] = 1;
	for (h = 0; h < m; h++)
		dfs2(-1, ii[h]);
	build(n);
	memset(gg, -1, n * sizeof *gg), cnt = 0;
	for (h = 0; h < m; h++) {
		i = ii[h];
		if (h >= m - 1 - h) {
			update(cnt - (m - 1 - h), cnt - 1, 1);
			dfs3(-1, i);
			update(cnt - (m - 1 - h), cnt - 1, -1);
		}
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (!path[j])
				update(cnt - 1 - dd[j], cnt - 1, 1);
		}
		g = gg[aa[i]], unique = 1;
		if (g >= 0) {
			push(n_ + g);
			if (mn[n_ + g] == 0)
				unique = 0;
		}
		if (unique)
			gg[aa[i]] = cnt, upd(cnt, 1);
		cnt++;
	}
	build(n);
	memset(gg, -1, n * sizeof *gg), cnt = 0;
	for (h = m - 1; h >= 0; h--) {
		i = ii[h];
		if (m - 1 - h > h) {
			update(cnt - h, cnt - 1, 1);
			dfs3(-1, i);
			update(cnt - h, cnt - 1, -1);
		}
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (!path[j])
				update(cnt - 1 - dd[j], cnt - 1, 1);
		}
		g = gg[aa[i]], unique = 1;
		if (g >= 0) {
			push(n_ + g);
			if (mn[n_ + g] == 0)
				unique = 0;
		}
		if (unique)
			gg[aa[i]] = cnt, upd(cnt, 1);
		cnt++;
	}
	for (i = 0; i < n; i++)
		printf("%d\n", ans[i]);
	return 0;
}

Compilation message

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

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 3 ms 540 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Incorrect 3 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 218 ms 12108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 386 ms 18924 KB Output is correct
2 Correct 449 ms 38056 KB Output is correct
3 Correct 55 ms 4884 KB Output is correct
4 Correct 481 ms 22584 KB Output is correct
5 Correct 468 ms 39664 KB Output is correct
6 Correct 503 ms 30764 KB Output is correct
7 Correct 678 ms 22484 KB Output is correct
8 Correct 516 ms 26164 KB Output is correct
9 Correct 486 ms 24908 KB Output is correct
10 Correct 474 ms 23884 KB Output is correct
11 Correct 802 ms 22804 KB Output is correct
12 Correct 499 ms 36264 KB Output is correct
13 Correct 490 ms 29960 KB Output is correct
14 Correct 512 ms 29896 KB Output is correct
15 Correct 1073 ms 23112 KB Output is correct
16 Correct 460 ms 34252 KB Output is correct
17 Correct 509 ms 31000 KB Output is correct

Subtask #4
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 3 ms 540 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Incorrect 3 ms 596 KB Output isn't correct
5 Halted 0 ms 0 KB -