oj.uz

Submission #120620

# Submission time Handle Problem Language Result Execution time Memory
120620 2019-06-25T05:55:02 Z 윤교준(#2960) Mergers (JOI19_mergers) C++14
0 / 100
 192 ms 58096 KB 
#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];

int prt[19][MAXN], prte[MAXN], dep[MAXN], cnt[MAXN], dfo[MAXN];
bitset<MAXN> usedE, chk;

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

int N, K, Ans;

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;
		prte[v] = e;
		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;
		usedE[prte[v]] = true;
		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; i < N; i++) if(!usedE[i]) {
		if(debug) {
			printf("EDGE %d %d\n", A[i], B[i]);
		}
		TG[A[i]].eb(B[i]);
		TG[B[i]].eb(A[i]);
	}
	for(int i = 1; i <= N; i++) if(!chk[i]) {
		int ret = f(i);
		if(1 < ret) Ans += (ret + 1) >> 1;
	}
	cout << Ans << endl;
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 37752 KB Output is correct
2 Correct 36 ms 37752 KB Output is correct
3 Incorrect 35 ms 37760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 37752 KB Output is correct
2 Correct 36 ms 37752 KB Output is correct
3 Incorrect 35 ms 37760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 37752 KB Output is correct
2 Correct 36 ms 37752 KB Output is correct
3 Incorrect 35 ms 37760 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 51988 KB Output is correct
2 Correct 135 ms 58096 KB Output is correct
3 Incorrect 37 ms 38272 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 37752 KB Output is correct
2 Correct 36 ms 37752 KB Output is correct
3 Incorrect 35 ms 37760 KB Output isn't correct
4 Halted 0 ms 0 KB -