Submission #1275285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275285		algoproclub	Šarenlist (COCI22_sarenlist)	C++20	110 / 110	14 ms	576 KiB

Main

// UUID: cfde2e3e-7ca3-4421-b0c5-bbcc98bfb5c3
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mod = 1000000007;
int elek[61][61];
vector<int> g[61];
vector<bool> done(61);
vector<int> parent(61);
vector<int> g2[15];
vector<bool> done2(15);

void dfs(int start, int cel) {
	if (start == cel) return;
	done[start] = true;
	for (int v : g[start]) {
		if (!done[v]) {
			dfs(v, cel);
			parent[v] = start;
		}
	}
	return;
}

void dfs2(int u) {
	done2[u] = true;
	for (int v : g2[u]) {
		if (!done2[v]) dfs2(v);
	}
	return;
}

int main() {
	int n, m;
	ll k;
	cin >> n >> m >> k;
	for (int i = 0; i < n - 1; i ++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		elek[u][v] = i;
		elek[v][u] = i;
	}
	vector<bitset<60>> vec(m);
	for (int i = 0; i < m; i ++) {
		fill(parent.begin(), parent.end(), -1);
		fill(done.begin(), done.end(), false);
		int u, v;
		cin >> u >> v;
		dfs(u, v);
		while (parent[v] != -1) {
			vec[i].set(elek[parent[v]][v]);
			v = parent[v];
		}
	//	cout << vec[i] << "\n";
	}
	ll ans = 0;
	for (int i = 0; i < (1 << m); i ++) {
		for (int j = 0; j < m; j ++) g2[j] = {};
		fill(done2.begin(), done2.end(), 0);
		bitset<15> b(i);
	//	cout << b << "\n";
		int comps = 0;
		vector<int> ms;
		for (int j = 0; j < m; j ++) {
			if (b.test(j)) {
				ms.push_back(j);
			} 
		}
		int si = ms.size();
		for (int j = 0; j < si - 1; j ++) {
			for (int l = j + 1; l < si; l ++) {
				bitset<60> o = (vec[ms[j]] & vec[ms[l]]);
				if (o.count() != 0) {
					g2[ms[j]].push_back(ms[l]);
					g2[ms[l]].push_back(ms[j]);
				}
			}
		}
		for (int c : ms) {
			if (!done2[c]) {
				comps ++;
				dfs2(c);
			}
		}
		bitset<60> benne(0);
		for (int c : ms) benne = (benne | vec[c]);
		int edges = n - 1 - benne.count();
		ll p = 1;
		for (int j = 0; j < comps + edges; j ++) {
			p *= k;
			p %= mod;
		}
	//	cout << p << "\n";
		if (b.count() % 2 == 0) ans += p;
		else ans -= p;
		ans %= mod;
	}
	ans = (ans + mod) % mod;
	cout << ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 65 / 65