제출 #120910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
120910		youngyojun	Mergers (JOI19_mergers)	C++11	100 / 100	1549 ms	161212 KiB

mergers

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
using namespace std;
typedef pair<int, int> pii;

const bool debug = 0;

const int MAXN = 500055;
const int MAXK = 500055;

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;

vector<int> G[MAXN], TG[MAXN];
vector<int> CV[MAXK];
bitset<MAXN> chk;

int prt[19][MAXN], dep[MAXN], cnt[MAXN], dfo[MAXN];

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

int N, K;

bool ison(int a, int b) {
	return dfo[a] <= dfo[b] && dfo[b] < dfo[a] + cnt[a];
}

int lca(int a, int b) {
	if(dep[a] > dep[b]) swap(a, b);
	const int dt = dep[b] - dep[a];
	for(int i = 19; i--;) if(dt & (1<<i))
		b = prt[i][b];
	if(a == b) return a;
	for(int i = 19; i--;) if(prt[i][a] != prt[i][b]) {
		a = prt[i][a];
		b = prt[i][b];
	}
	return prt[0][a];
}

void dfs(int i, int &c) {
	c++; dfo[i] = c; cnt[i] = 1;
	for(int e : G[i]) {
		int v = A[e] ^ B[e] ^ i;
		if(dep[v]) continue;
		dep[v] = dep[i] + 1;
		prt[0][v] = i;
		dfs(v, c);
		cnt[i] += cnt[v];
	}
}

void getTree(vector<int> &V, vector<pii> &RV) {
	int n = sz(V);
	if(n < 2) return;

	sort(allv(V), [&](int a, int b) { return dfo[a] < dfo[b]; });
	vector<int> TV = V;
	for(int i = 1; i < n; i++) TV.eb(lca(V[i-1], V[i]));
	sort(allv(TV), [&](int a, int b) { return dfo[a] < dfo[b]; });
	univ(TV);

	vector<int> PQ;
	for(int v : TV) {
		for(; !PQ.empty() && !ison(PQ.back(), v); PQ.pop_back());
		if(!PQ.empty()) RV.eb(PQ.back(), v);
		PQ.eb(v);
	}
}

void drawEdge(int p, int v) {
	for(;;) {
		v = djf.uf(v);
		if(dep[v] <= dep[p]) break;
		djf.uf(prt[0][v], v);
	}
}

int f(int i) {
	int ret = 0;
	chk[i] = true;
	for(int v : TG[i]) if(!chk[v]) {
		ret += f(v);
	}
	if(1 == sz(TG[i])) ret++;
	return ret;
}

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

	cin >> N >> K;
	for(int i = 1; i < N; i++) {
		cin >> A[i] >> B[i];
		if(A[i] > B[i]) swap(A[i], B[i]);
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}
	for(int i = 1; i <= N; i++) {
		cin >> C[i];
		CV[C[i]].eb(i);
	}

	dep[1] = 1; { int c = 0; dfs(1, c); }
	for(int j = 1; j < 19; j++) for(int i = 1; i <= N; i++)
		prt[j][i] = prt[j-1][prt[j-1][i]];

	for(int i = 1; i <= K; i++) {
		vector<pii> TV;
		getTree(CV[i], TV);
		for(auto &e : TV) drawEdge(e.first, e.second);

		if(debug) {
			printf("color %d\n", i);
			for(auto &e : TV) printf("(%d,%d) ", e.first, e.second);
			puts("");
		}
	}

	for(int i = 1, a, b; i < N; i++) {
		a = djf.uf(A[i]); b = djf.uf(B[i]);
		if(a == b) continue;
		TG[a].eb(b);
		TG[b].eb(a);
	}
	cout << ((f(1) + 1) >> 1) << endl;
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30