Submission #529017

# Submission time Handle Problem Language Result Execution time Memory
529017 2022-02-21T23:02:41 Z penguinhacker Šarenlist (COCI22_sarenlist) C++14
110 / 110
12 ms 320 KB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int M=1e9+7;
int n, m, k;
vector<ar<int, 2>> adj[60];
vector<int> cur, e[15];
ll a2[60], kp[60];
bool vis[60];

void dfs(int u, int p, int t, int i) {
	if (u==t) {
		e[i]=cur;
		return;
	}
	for (ar<int, 2> v : adj[u]) {
		if (v[0]==p)
			continue;
		cur.push_back(v[1]);
		dfs(v[0], u, t, i);
		cur.pop_back();
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
	}
	for (int i=0; i<m; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		dfs(u, -1, v, i);
	}
	kp[0]=1;
	for (int i=1; i<n; ++i)
		kp[i]=kp[i-1]*k%M;
	ll ans=0;
	for (int i=0; i<(1<<m); ++i) {
		memset(a2, 0, sizeof(a2));
		for (int j=0; j<m; ++j)
			if (i&1<<j)
				for (int x=1; x<e[j].size(); ++x) {
					a2[e[j][0]]|=1ll<<e[j][x];
					a2[e[j][x]]|=1ll<<e[j][0];
				}
		memset(vis, 0, sizeof(vis));
		int cmp=0;
		for (int i=1; i<n; ++i) {
			if (vis[i])
				continue;
			++cmp;
			ll all=0, q=1ll<<i;
			while(all!=q) {
				int bit=__builtin_ctzll(all^q);
				vis[bit]=1;
				all|=1ll<<bit;
				q|=a2[bit];
			}
		}
		ans=(ans+(__builtin_popcount(i)%2==0?1:-1)*kp[cmp]+M)%M;
	}
	cout << ans;
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int x=1; x<e[j].size(); ++x) {
      |                   ~^~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 312 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 2 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 316 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 2 ms 204 KB Output is correct
18 Correct 1 ms 320 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 312 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 2 ms 204 KB Output is correct
25 Correct 2 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 6 ms 312 KB Output is correct
28 Correct 0 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 6 ms 316 KB Output is correct
31 Correct 2 ms 204 KB Output is correct
32 Correct 1 ms 204 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 4 ms 204 KB Output is correct
36 Correct 12 ms 204 KB Output is correct
37 Correct 6 ms 204 KB Output is correct