Submission #104752

#	Time	Username	Problem	Language	Result	Execution time	Memory
104752		Just_Solve_The_Problem	Mergers (JOI19_mergers)	C++11	100 / 100	2298 ms	155000 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

const int N = (int)5e5 + 7;

struct DSU {
	int par[N];
	int siz[N];
	DSU() {
		iota(par, par + N, 0);
		fill(siz, siz + N, 1);
	}
	int getpar(int a) {
		if (par[a] == a) return a;
		return par[a] = getpar(par[a]);
	}
	void connect(int a, int b) {
		a = getpar(a);
		b = getpar(b);
		if (a != b) {
			if (siz[a] > siz[b]) swap(a, b);
			par[a] = b;
			siz[b] += siz[a];
		}
	}
};
DSU dsu;

int n, k;
vector < int > gr[N];
int st[N], s[N], sb[N], prs[N];
int deg[N], tin[N], tout[N];
int lc[20][N];
int tiktak;
vector < int > vec[N];

bool upper(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
	if (upper(a, b)) return a;
	if (upper(b, a)) return b;
	for (int i = 19; i >= 0; i--) {
		if (!upper(lc[i][a], b)) a = lc[i][a];
	}
	return lc[0][a];
}

void precalc(int v, int pr) {
	tin[v] = ++tiktak;
	lc[0][v] = pr;
	for (int i = 1; i < 20; i++) {
		lc[i][v] = lc[i - 1][lc[i - 1][v]];
	}
	for (int to : gr[v]) {
		if (to == pr) continue;
		precalc(to, v);
	}
	tout[v] = tiktak;
}

void dfs(int v, int pr) {
	sb[prs[s[v]]]++;
	for (int to : gr[v]) {
		if (to == pr) continue;
		dfs(to, v);
		st[v] += (st[to] - sb[to]);
		if (st[to] - sb[to] > 0) {
			dsu.connect(v, to);
		}
	}
	st[v]++;
}

main() {
	scanf("%d %d", &n, &k);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		gr[u].push_back(v);
		gr[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%d", &s[i]);
		vec[s[i]].push_back(i);
	}
	precalc(1, 1);
	for (int i = 1; i <= k; i++) {
		int v = vec[i][0];
		for (int j = 1; j < vec[i].size(); j++) {
			v = lca(v, vec[i][j]);
		}
		prs[i] = v;
	}
	dfs(1, 1);
	for (int i = 1; i <= n; i++) {
		for (int to : gr[i]) {
			if (dsu.getpar(i) != dsu.getpar(to)) {
				deg[dsu.getpar(i)]++;
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += (deg[i] == 1);
	}
	cout << (ans + 1) / 2;
}

Compilation message (stderr)

mergers.cpp:77:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
mergers.cpp: In function 'int main()':
mergers.cpp:92:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < vec[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~
mergers.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
mergers.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s[i]);
   ~~~~~^~~~~~~~~~~~~

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