Submission #121322

#	Time	Username	Problem	Language	Result	Execution time	Memory
121322		youngyojun	Unique Cities (JOI19_ho_t5)	C++11	100 / 100	807 ms	62276 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;

const int MAXN = 200055;
const int MAXM = 200055;

struct DJF {
	DJF() { init(); }
	int ud[MAXN];

	void init() { iota(ud, ud+MAXN, 0); }
	int uf(int i) { return i == ud[i] ? i : (ud[i] = uf(ud[i])); }
	void uf(int a, int b) { ud[uf(b)] = uf(a); }
} djf;

struct NOD {
	NOD() { init(); }

	DJF djf;

	int A[MAXN], B[MAXM];
	int L, C;

	void init() {
		djf.init();
		fill(A, A+MAXN, 0);
		fill(B, B+MAXM, 0);
		L = C = 0;
	}
	void push(int x) {
		L++;
		A[L] = x;
		B[x]++;
		if(1 == B[x]) C++;
		djf.ud[L] = L;
	}
	void pop() {
		if(djf.uf(L) == L) {
			int x = A[L];
			B[x]--;
			if(!B[x]) C--;
		}
		L--;
	}
	void f(int s, int e) {
		for(int x;;) {
			e = djf.uf(e);
			if(e < s) break;
			x = A[e];
			B[x]--;
			if(!B[x]) C--;
			djf.uf(e-1, e);
		}
	}
	void g(int i) {
		if(djf.uf(i) != i) {
			djf.ud[i] = i;
			int x = A[i];
			B[x]++;
			if(1 == B[x]) C++;
		}
	}
	int get() { return C; }
} nod;

vector<int> G[MAXN], T[MAXN];

int prt[MAXN], dep[MAXN], dmx[MAXN];

int A[MAXN];

int Ans[MAXN], PAns[MAXN];
int N, M, TA, TB;

void dfs(int i) {
	dmx[i] = dep[i];
	for(int v : G[i]) {
		if(dep[v]) continue;
		dep[v] = dep[i] + 1;
		prt[v] = i;
		dfs(v);
		upmax(dmx[i], dmx[v]);
	}
}

void f(int v) {
	nod.push(A[v]);
	int d1 = T[v].empty() ? 0 : dmx[T[v][0]] - dep[v];
	int d2 = sz(T[v]) < 2 ? 0 : dmx[T[v][1]] - dep[v];
	if(!T[v].empty()) {
		nod.f(max(1, dep[v]-d2), dep[v]-1);
		f(T[v][0]);
		nod.g(dep[v]);
	}
	if(1 < sz(T[v])) {
		for(int i = 1, n = sz(T[v]); i < n; i++) {
			nod.f(max(1, dep[v]-d1), dep[v]-1);
			f(T[v][i]);
			nod.g(dep[v]);
		}
	}
	nod.f(max(1, dep[v]-d1), dep[v]-1);
	nod.pop();
	Ans[v] = nod.get();
}

void solve(int Rt) {
	fill(dep, dep+N+1, 0);
	fill(prt, prt+N+1, 0);
	dep[Rt] = 1; dfs(Rt);

	nod.init();

	for(int i = 1; i <= N; i++) T[i].clear();
	for(int i = 1; i <= N; i++) {
		for(int v : G[i]) {
			if(v == prt[i]) continue;
			T[i].eb(v);
		}
		sort(allv(T[i]), [&](int a, int b) {
			return dmx[a] > dmx[b];
		});
	}

	f(Rt);
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for(int i = 1, a, b; i < N; i++) {
		cin >> a >> b;
		G[a].eb(b);
		G[b].eb(a);
	}
	for(int i = 1; i <= N; i++) cin >> A[i];

	dep[1] = 1; dfs(1);
	TA = int(max_element(dep+1, dep+N+1) - dep);
	fill(dep, dep+N+1, 0);
	dep[TA] = 1; dfs(TA);
	TB = int(max_element(dep+1, dep+N+1) - dep);

	solve(TA);
	for(int i = 1; i <= N; i++) swap(Ans[i], PAns[i]);
	solve(TB);

	for(int i = 1; i <= N; i++) printf("%d\n", max(Ans[i], PAns[i]));
	return 0;
}

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