Submission #1300941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300941		Jawad_Akbar_JJ	Šarenlist (COCI22_sarenlist)	C++20	45 / 110	1094 ms	580 KiB

Main

#include <iostream>
#include <vector>

using namespace std;
const int N = 70, mod = 1e9 + 7;
int hei[N], col[N], c[N], d[N], Par[N], final_Ans;
vector<int> nei[N];

void dfs(int u, int h){
	hei[u] = h;
	for (int i : nei[u]){
		if (i == Par[u])
			continue;
		Par[i] = u;
		dfs(i, h + 1);
	}
}

int main(){
	int n, m, k;
	cin>>n>>m>>k;

	for (int i=1;i<n;i++){
		int a, b;
		cin>>a>>b;
		nei[a].push_back(b);
		nei[b].push_back(a);
	}

	for (int j=0;j<m;j++)
		cin>>c[j]>>d[j];

	dfs(1, 1);

	for (int mask = 0;mask < (1<<m);mask++){
		for (int i=1;i<=n;i++)
			col[i] = 0;

		for (int j=0;j<m;j++){
			if ((1<<j) & mask){
				int u = c[j], v = d[j];
				if (hei[u] > hei[v])
					swap(u, v);
				while (hei[v] > hei[u])
					col[v] |= 1<<j, v = Par[v];
				while (u != v)
					col[v] |= 1<<j, col[u] |= 1<<j, u = Par[u], v = Par[v];
			}
		}

		for (int l=1;l<=n;l++){
			for (int i=1;i<=n;i++){
				for (int j=1;j<=n;j++)
					if (col[i] & col[j])
						col[i] = col[j] = col[i] | col[j];
			}
		}

		int msk = 0, Ans = 1;
		for (int i=2;i<=n;i++){
			if ((msk & col[i]) == 0)
				Ans = 1LL * Ans * k % mod;
			msk |= col[i];
		}

		if (__builtin_popcount(mask) % 2 == 1)
			final_Ans = (final_Ans - Ans + mod) % mod;
		else
			final_Ans = (final_Ans + Ans) % mod;
	}
	cout<<final_Ans<<'\n';
}

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