Submission #1275297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275297		kaiboy	Unique Cities (JOI19_ho_t5)	C++20	100 / 100	241 ms	47108 KiB

joi2019_ho_t5

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 200000;

int *ej[N], eo[N], aa[N];
int dds[N], ddt[N], *dd, d_, i_;
int hh[N], ii_[N], ans[N];
int *ej_[N], eo_[N], ii[N], rr_[N], pp_[N], qq_[N], n_;
int kk[N], c, cc[N];

void append(int **ej, int *eo, int i, int j) {
	int o = eo[i]++;
	if (!o)
		ej[i] = (int *) malloc(sizeof *ej[i]);
	else if (!(o & o - 1))
		ej[i] = (int *) realloc(ej[i], (o << 1) * sizeof *ej[i]);
	ej[i][o] = j;
}

void dfs0(int p, int i, int d) {
	if (d_ < d)
		d_ = d, i_ = i;
	dd[i] = d++;
	for (int o = 0; o < eo[i]; o++) {
		int j = ej[i][o];
		if (j != p)
			dfs0(i, j, d);
	}
}

int dfs1(int p, int i) {
	int h = 0;
	for (int o = 0; o < eo[i]; o++) {
		int j = ej[i][o];
		if (j != p)
			h = max(h, dfs1(i, j) + 1);
	}
	return hh[i] = h;
}

void dfs2(int p, int i, int i_) {
	if (dds[i] >= ddt[i]) {
		int i__ = i_;
		while (i__ && dds[ii[i__]] >= dds[i] - hh[i])
			if (qq_[i__] && dds[ii[qq_[i__]]] >= dds[i] - hh[i])
				i__ = qq_[i__];
			else
				i__ = pp_[i__];
		ii_[i] = i__;
	}
	int h0 = 0, h1 = 0;
	for (int o = 0; o < eo[i]; o++) {
		int j = ej[i][o];
		if (j != p) {
			int h = hh[j] + 1;
			if (h0 < h)
				h1 = h0, h0 = h;
			else if (h1 < h)
				h1 = h;
		}
	}
	for (int o = 0; o < eo[i]; o++) {
		int j = ej[i][o];
		if (j != p) {
			int h = hh[j] + 1 == h0 ? h1 : h0;
			int i__ = i_;
			while (i__ && dds[ii[i__]] >= dds[i] - h)
				if (qq_[i__] && dds[ii[qq_[i__]]] >= dds[i] - h)
					i__ = qq_[i__];
				else
					i__ = pp_[i__];
			ii[n_] = i;
			append(ej_, eo_, pp_[n_] = i__, n_);
			if (rr_[pp_[n_]] == rr_[qq_[pp_[n_]]]) {
				rr_[n_] = rr_[pp_[n_]] + 1;
				qq_[n_] = qq_[qq_[pp_[n_]]];
			} else {
				rr_[n_] = 0;
				qq_[n_] = pp_[n_];
			}
			dfs2(i, j, n_++);
		}
	}
}

void dfs3(int i) {
	if (i) {
		int a = aa[ii[i]];
		if (!kk[a]++)
			c++;
	}
	cc[i] = c;
	for (int o = 0; o < eo_[i]; o++) {
		int j = ej_[i][o];
		dfs3(j);
	}
	if (i) {
		int a = aa[ii[i]];
		if (!--kk[a])
			c--;
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, a_; cin >> n >> a_;
	for (int h = 0; h < n - 1; h++) {
		int i, j; cin >> i >> j, i--, j--;
		append(ej, eo, i, j), append(ej, eo, j, i);
	}
	for (int i = 0; i < n; i++)
		cin >> aa[i], aa[i]--;
	dd = dds, d_ = -1, dfs0(-1, 0, 0); int s = i_;
	dd = dds, d_ = -1, dfs0(-1, s, 0); int t = i_;
	dd = ddt, dfs0(-1, t, 0);
	dfs1(-1, s);
	ii[n_++] = -1;
	dfs2(-1, s, 0);
	dfs3(0);
	for (int i = 0; i < n; i++)
		if (dds[i] > ddt[i])
			ans[i] = cc[ii_[i]];
	dfs1(-1, t);
	for (int i = 0; i < n; i++) {
		swap(dds[i], ddt[i]);
		if (eo_[i])
			free(ej_[i]), eo_[i] = 0;
	}
	n_ = 0, ii[n_++] = -1;
	dfs2(-1, t, 0);
	dfs3(0);
	for (int i = 0; i < n; i++)
		if (dds[i] >= ddt[i])
			ans[i] = cc[ii_[i]];
	for (int i = 0; i < n; i++)
		cout << ans[i] << '\n';
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32