Submission #706515

#	Time	Username	Problem	Language	Result	Execution time	Memory
706515		rainboy	Unique Cities (JOI19_ho_t5)	C11	32 / 100	1073 ms	39664 KiB

joi2019_ho_t5

#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 (stderr)

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
• Subtask 2: 0 / 32
• Subtask 3: 32 / 32
• Subtask 4: 0 / 32