oj.uz

Submission #851447

# Submission time Handle Problem Language Result Execution time Memory
851447 2023-09-19T19:00:54 Z serifefedartar Šarenlist (COCI22_sarenlist) C++17
110 / 110
 21 ms 756 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20;
const ll MAXN = 2e5 + 5;

vector<vector<pair<int,int>>> graph;
vector<vector<int>> edges;
bool found = false;
void dfs(int node, int parent, int target, int idx) {
	if (node == target) {
		found = true;
		return ;
	}

	if (found)
		return ;

	for (auto u : graph[node]) {
		if (found)
			return ;

		if (u.f != parent) {
			edges[idx].push_back(u.s);
			dfs(u.f, node, target, idx);
			if (!found)
				edges[idx].pop_back();
			else
				break;
		}
	}
}

ll expo(ll a, ll b) {
	ll res = 1;
	while (b) {
		if (b & 1)
			res = (res * a) % MOD;
		a = (a * a) % MOD;
		b /= 2;
	}
	return res;
}

int par[65], sz[65], par2[65], sz2[65];
int find(int node) {
	if (par[node] == node)
		return node;
	return par[node] = find(par[node]);
}

int find2(int node) {
	if (par2[node] == node)
		return node;
	return par2[node] = find2(par2[node]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)
		return ;
	sz[a] += sz[b];
	par[b] = a; 
}

void unite2(int a, int b) {
	a = find2(a);
	b = find2(b);
	if (a == b)
		return ;
	sz2[a] += sz2[b];
	par2[b] = a;
}

void dsu() {
	for (int i = 0; i <= 62; i++)
		par[i] = i, sz[i] = 1;
}

void dsu2() {
	for (int i = 0; i <= 62; i++)
		par2[i] = i, sz2[i] = 1;
}

int main() {
	fast
	ll n, m, k, a, b;
	cin >> n >> m >> k;

	graph = vector<vector<pair<int,int>>>(n+1, vector<pair<int,int>>());
	edges = vector<vector<int>>(m, vector<int>());
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		graph[a].push_back({b, i});
		graph[b].push_back({a, i});
	}

	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		found = false;
		dfs(a, a, b, i);
	}

	dsu();
	for (int i = 0; i < m; i++) {
		for (auto u : edges[i])
			unite(0, u);
	}

	ll ans = 0;
	const int mx_mask = (1<<m);
	for (int msk = 0; msk < mx_mask; msk++) {
		dsu(); dsu2();
		for (int j = 0; j < m; j++) {
			if (((1<<j) & msk) == 0)
				continue;
			for (auto u : edges[j])
				unite(0, u);
			for (int i = 0; i < edges[j].size() - 1; i++)
				unite2(edges[j][i], edges[j][i+1]);
		}
		

		ll cnt = 0;
		for (int i = 1; i <= n-1; i++)
			cnt += (i == find2(i) && find(i) == 0);

		int s = sz[0] - 1;
		if (__builtin_popcount(msk) % 2 == 0)
			ans = (ans + expo(k, n-1-s) * expo(k, cnt)) % MOD;
		else {
			ans = (ans - expo(k, n-1-s) * expo(k, cnt) % MOD) % MOD;
			while (ans < 0)
				ans += MOD;
		}
	}
	cout << ans << "\n";
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:125:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |    for (int i = 0; i < edges[j].size() - 1; i++)
      |                    ~~^~~~~~~~~~~~~~~~~~~~~

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 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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