Submission #696631

#	Time	Username	Problem	Language	Result	Execution time	Memory
696631		TranGiaHuy1508	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	24 ms	324 KiB

Main

#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

#define int long long
const int mod = 1e9 + 7;

struct DSU{
	vector<int> parent, size;

	DSU(int N){
		parent.resize(N); iota(parent.begin(), parent.end(), 0);
		size.assign(N, 1);
	}

	int get(int x){
		return (x == parent[x]) ? x : (parent[x] = get(parent[x]));
	}

	bool merge(int a, int b){
		a = get(a); b = get(b);
		if (a == b) return false;
		if (size[a] < size[b]) swap(a, b);
		parent[b] = a; size[a] += size[b];
		return true;
	}
};

int binpow(int n, int a){
	int res = 1;
	for (int exp = n; a; a >>= 1, exp = exp * exp % mod){
		if (a & 1) res = res * exp % mod;
	}
	return res;
}

int n, m, K;
vector<int> crr;
vector<vector<int>> lst;
vector<vector<pair<int, int>>> adj;
vector<pair<int, int>> qs;

void dfs(int x, int target, int p = -1){
	if (x == target) lst.push_back(crr);
	for (auto [k, idx]: adj[x]){
		if (k == p) continue;
		crr.push_back(idx);
		dfs(k, target, x);
		crr.pop_back();
	}
}

void main_program(){
	cin >> n >> m >> K;

	adj.resize(n);
	qs.resize(m);

	for (int i = 0; i < n-1; i++){
		int a, b; cin >> a >> b;
		a--; b--;
		adj[a].emplace_back(b, i);
		adj[b].emplace_back(a, i);
	}

	for (int i = 0; i < m; i++){
		int c, d; cin >> c >> d;
		c--; d--;
		qs[i] = {c, d};
	}

	for (auto [x, y]: qs) dfs(x, y);

	int res = 0;
	for (int mask = 0; mask < (1 << m); mask++){
		DSU dsu(n-1);
		int cc = n-1;
		for (int i = 0; i < m; i++){
			if ((mask >> i) & 1){
				for (int j = 1; j < (int)lst[i].size(); j++){
					if (dsu.merge(lst[i][j-1], lst[i][j])) cc--;
				}
			}
		}
		int sign = (__builtin_popcountll(mask) & 1) ? -1 : 1;
		res += sign * binpow(K, cc);
		res %= mod;
	}

	cout << (res % mod + mod) % mod << "\n";
}

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