Submission #995230

#	Time	Username	Problem	Language	Result	Execution time	Memory
995230		duckindog	Mergers (JOI19_mergers)	C++17	0 / 100	1 ms	604 KiB

mergers

#include <bits/stdc++.h>

using namespace std;

const int N = 100 + 10;
int n, k;
vector<int> ad[N];
int s[N];
int state[N];

int par[N], st[N], ed[N], it;
void dfs(int u, int p = -1) { 
	st[u] = ++it;
	for (const auto& v : ad[u]) { 
		if (v == p) continue;
		par[v] = u;
		dfs(v, u);
	}
	ed[u] = it;
}
bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }

int32_t main() { 
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> k;
	for (int i = 1; i < n; ++i) { 
		int u, v; cin >> u >> v;
		ad[u].push_back(v);
		ad[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i) cin >> s[i];

	dfs(1);

	auto chk = [&](int group) { 
		for (int i = 1; i <= n; ++i) { 
			for (int j = 1; j < i; ++j) { 
				if ((group >> state[i] - 1 & 1) != (group >> state[j] - 1 & 1)) continue;
				int u = i, v = j;
				
				while (true) { 
					if ((group >> state[u] - 1 & 1) != (group >> state[i] - 1 & 1)) return false;
					if (anc(u, v)) break;
					u = par[u];
				}
				while (true) { 
					if ((group >> state[v] - 1 & 1) != (group >> state[i] - 1 & 1)) return false;
					if (v == u) break;
					v = par[v];
				}
			}
		}
		return true;
	};

	int answer = 1'000'000;
	for (int merge = 0; merge < (1 << k); ++merge) { 
		int root = 0, mask = 0;
		for (int i = 1; i <= n; ++i) {
			state[i] = s[i];
			if (merge >> s[i] - 1 & 1) { 
				root = (!root ? s[i] : root);
				state[i] = root;
			}
			mask |= (1 << state[i] - 1);
		}
		bool separable = false; 
		for (int group = 1; group < mask; ++group) { 
			bool valid = true;
			for (int i = 1; i <= n; ++i)
				for (int j = 1; j < i; ++j)
					if ((group >> state[i] - 1 & 1) != (group >> state[j] - 1 & 1) && state[i] == state[j]) {
						valid = false;
					}

			if (!valid) continue;
			separable |= chk(group);
		}
		if (!separable) answer = min(answer, max(0, __builtin_popcount(merge) - 1));
	}
	cout << answer << "\n";
}

Compilation message (stderr)

mergers.cpp: In lambda function:
mergers.cpp:39:28: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   39 |     if ((group >> state[i] - 1 & 1) != (group >> state[j] - 1 & 1)) continue;
      |                   ~~~~~~~~~^~~
mergers.cpp:39:59: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   39 |     if ((group >> state[i] - 1 & 1) != (group >> state[j] - 1 & 1)) continue;
      |                                                  ~~~~~~~~~^~~
mergers.cpp:43:29: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   43 |      if ((group >> state[u] - 1 & 1) != (group >> state[i] - 1 & 1)) return false;
      |                    ~~~~~~~~~^~~
mergers.cpp:43:60: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   43 |      if ((group >> state[u] - 1 & 1) != (group >> state[i] - 1 & 1)) return false;
      |                                                   ~~~~~~~~~^~~
mergers.cpp:48:29: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   48 |      if ((group >> state[v] - 1 & 1) != (group >> state[i] - 1 & 1)) return false;
      |                    ~~~~~~~~~^~~
mergers.cpp:48:60: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   48 |      if ((group >> state[v] - 1 & 1) != (group >> state[i] - 1 & 1)) return false;
      |                                                   ~~~~~~~~~^~~
mergers.cpp: In function 'int32_t main()':
mergers.cpp:62:22: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   62 |    if (merge >> s[i] - 1 & 1) {
      |                 ~~~~~^~~
mergers.cpp:66:27: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   66 |    mask |= (1 << state[i] - 1);
      |                  ~~~~~~~~~^~~
mergers.cpp:73:29: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   73 |      if ((group >> state[i] - 1 & 1) != (group >> state[j] - 1 & 1) && state[i] == state[j]) {
      |                    ~~~~~~~~~^~~
mergers.cpp:73:60: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   73 |      if ((group >> state[i] - 1 & 1) != (group >> state[j] - 1 & 1) && state[i] == state[j]) {
      |                                                   ~~~~~~~~~^~~

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