oj.uz

Submission #696631

# Submission time Handle Problem Language Result Execution time Memory
696631 2023-02-07T02:13:05 Z TranGiaHuy1508 Šarenlist (COCI22_sarenlist) C++17
110 / 110
 24 ms 324 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 3 ms 212 KB Output is correct
6 Correct 3 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #5
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 2 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 3 ms 212 KB Output is correct
25 Correct 3 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 9 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 10 ms 324 KB Output is correct
31 Correct 3 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 2 ms 212 KB Output is correct
35 Correct 5 ms 212 KB Output is correct
36 Correct 24 ms 212 KB Output is correct
37 Correct 11 ms 320 KB Output is correct