Submission #104751

#	Time	Username	Problem	Language	Result	Execution time	Memory
104751		Just_Solve_The_Problem	Mergers (JOI19_mergers)	C++11	0 / 100	106 ms	21444 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 cnt[N], s[N], szs[N];
int used[N], deg[N];

void bfs(int v, int pr) {
	queue < int > q;
	q.push(v);
	used[v] = 1;
	int sz = 0;
	while (!q.empty()) {
		v = q.front();
		q.pop();
		cnt[s[v]]++;
		if (cnt[s[v]] == 1) {
			sz++;
		}
		if (cnt[s[v]] == szs[s[v]]) {
			sz--;
		}
		for (int i = 0; i < gr[v].size() && sz > 0; i++) {
			int to = gr[v][i];
			if (used[to]) continue;
			used[to] = 1;
			q.push(to);
			dsu.connect(v, to);
		}
	}
}

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]);
		szs[s[i]]++;
	}
	for (int i = 1; i <= n; i++) {
		if (!used[i]) {
			bfs(i, i);
		}
	}
	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: In function 'void bfs(int, int)':
mergers.cpp:50:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < gr[v].size() && sz > 0; i++) {
                   ~~^~~~~~~~~~~~~~
mergers.cpp: At global scope:
mergers.cpp:60:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
mergers.cpp: In function 'int main()':
mergers.cpp:61: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:64: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:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &s[i]);
   ~~~~~^~~~~~~~~~~~~

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