oj.uz

Submission #880638

# Submission time Handle Problem Language Result Execution time Memory
880638 2023-11-29T18:51:04 Z tsumondai Šarenlist (COCI22_sarenlist) C++14
110 / 110
 13 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 60+5;

const int oo = 1e9, mod = 1e9 + 7;

int n, m, k, parent[N], depth[N], path[N], uf[N], union_mask[N];
vector<int> adj[N];

int add(int a, int b) {
	a += b;
	if (a >= mod) a -= mod;
	return a;
}

int sub(int a, int b) {
	a -= b;
	if (a < 0) a += mod;
	return a;
}

int mul(int a, int b) {
	return (a * b) % mod;
}

int popcount(long long x){
    int res=0;
    for(;x;x>>=1){
        if(x&1) res++;
    }
    return res;
}

long long binpow(long long a, long long b) {
	a %= mod;
	long long res = 1;
	while (b > 0) {
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

void dfs(int node, int p = -1, int d = 0) {
	parent[node] = p;
	depth[node] = d;
	for (int i : adj[node]) {
		if (i != p) dfs(i, node, d + 1);
	}
}

void mark_path(int idx, int u, int v) {
	if (depth[u] < depth[v]) swap(u, v);
	for (; depth[u] > depth[v]; u = parent[u]) {
		path[idx] |= (1LL << u);
	}
	for (; u != v; u = parent[u], v = parent[v]) {
		path[idx] |= (1LL << v);
		path[idx] |= (1LL << u);
	}
}


int fnd(int a) {
	return uf[a] = (uf[a] == a ? a : fnd(uf[a]));
}
void un(int a, int b) {
	a = fnd(a);
	b = fnd(b);
	uf[a] = b;
	union_mask[b] |= union_mask[a];
}
void reset_uf() {
	for (int i = 0; i < m; i++) uf[i] = i;
	for (int i = 0; i < m; i++) union_mask[i] = path[i];
}

int compute(int mask) {
	reset_uf();
	for (int i = 0; i < m; i++) {
		if (!(mask & (1 << i))) continue;
		for (int j = i + 1; j < m; j++) {
			if (!(mask & (1 << j))) continue;
			if (path[i] & path[j]) {
				un(i, j);
			}
		}
	}
	int cnt = 0;
	int not_on_paths = n - 1;
	for (int i = 0; i < m; i++) {
		if (!(mask & (1 << i))) continue;
		if (i != uf[i]) continue;
		cnt++;
		not_on_paths -= popcount(union_mask[i]);
	}
	return binpow(k, cnt + not_on_paths);
}

void process() {
	cin >> n >> m >> k;
	foru(i, 1, n - 1) {
		int u, v; cin >> u >> v;
		adj[u].pb(v); adj[v].pb(u);
	}
	dfs(1);
	foru(i, 0, m - 1) {
		int c, d; cin >> c >> d;
		mark_path(i, c, d);
	}
	int res = 0;
	foru(mask, 0, (1 << m) - 1) {
		int popcorn = popcount(mask);
		if (popcorn % 2 == 0) {
			res = add(res, compute(mask));
		} else {
			res = sub(res, compute(mask));
		}
	}
	cout << res;
	return;
}

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	//freopen(".inp", "r", stdin);
	//freopen(".out", "w", stdout);
	process();
	cerr << "Time elapsed: " << __TIME << " s.\n";
	return 0;
}

/*
Xét các trường hợp đặc biệt
Kiểm tra lại input/output
Cố gắng trâu
Lật ngược bài toán
Keep calm and get VOI
Flow:

*/

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
65.0 / 65.0

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