Submission #374717

#	Time	Username	Problem	Language	Result	Execution time	Memory
374717		guka415	Mergers (JOI19_mergers)	C++14	0 / 100	81 ms	37092 KiB

mergers

#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define mp make_pair

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <bitset>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int sz = 6e5;
vector<int> adj[sz], reglst[sz];
int n, k;
int ufp[sz], reg[sz], dep[sz], treepar[sz], deg[sz];

void dfs(int src, int prv) {
	for (int x : adj[src]) {
		if (x != prv) {
			treepar[x] = src;
			dep[x] = dep[src] + 1;
			dfs(x, src);
		}
	}
}

int getpar(int src) {
	if (src == ufp[src])return src;
	return ufp[src] = getpar(ufp[src]);
}

void unite(int a, int b) {
	int para = getpar(a), parb = getpar(b);
	if (para != parb) {
		if (dep[para] < dep[parb])swap(para, parb);
		ufp[para] = parb;
	}
}

int main() {
	fast;
	cin >> n >> k;
	foru(i, 0, n - 1) {
		int x, y;
		cin >> x >> y;
		adj[--x].pb(--y);
		adj[y].pb(x);
	}
	foru(i, 0, n) {
		cin >> reg[i]; reglst[reg[i]].pb(i);
		ufp[i] = i;
	}
	treepar[0] = -1;
	dfs(0, -1);
	for (int r = 1; r <= k; r++) {
		for (int j = 1; j < reglst[r].size(); j++) {
			int x = getpar(reglst[r][0]), y = getpar(reglst[r][j]);
			while (x != y) {
				if (dep[x] < dep[y]) {
					unite(y, treepar[y]);
					y = getpar(y);
				}
				else {
					unite(x, treepar[x]);
					x = getpar(x);
				}
			}
		}
	}
	foru(i, 0, n) {
		for (int x : adj[i]) {
			if (dep[x] > dep[i])
				deg[getpar(x)]++, deg[getpar(i)]++;
		}
	}
	int ret = 0;
	foru(i, 0, n)
		ret += (deg[i] == 1 && getpar(i) == i);
	cout << (ret + 1) / 2 << '\n';
	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (int j = 1; j < reglst[r].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~

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