Submission #529017

#	Time	Username	Problem	Language	Result	Execution time	Memory
529017		penguinhacker	Šarenlist (COCI22_sarenlist)	C++14	110 / 110	12 ms	320 KiB

Main

#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 (stderr)

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) {
      |                   ~^~~~~~~~~~~~

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