제출 #1270468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270468		algoproclub	Šarenlist (COCI22_sarenlist)	C++20	110 / 110	22 ms	328 KiB

Main

// UUID: fd4a6981-f927-4fe2-891b-55d536a77736
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<pair<int, int> > > g;
vector<vector<int> > eg;
const int MOD = 1e9 + 7;
vector<int> path;
vector<bool> vis;
void con(int v)
{
	vis[v] = 1;
	for(auto x : eg[v]) if(!vis[x]) con(x);
}
bool dfs(int v, int p, int go)
{
	if(v == go) return 1;
	for(auto [x, ind] : g[v])
	{
		if(x == p) continue;
		path.push_back(ind);
		if(dfs(x, v, go)) return 1;
	}
	if(!path.empty()) path.pop_back();
	return 0;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n, m, k;
	cin >> n >> m >> k;
	g.resize(n + 1);
	eg.resize(n);
	for(int i = 0; i < n - 1; i++)
	{
		int x, y;
		cin >> x >> y;
		g[x].push_back({y, i});
		g[y].push_back({x, i});
	}
	vector<vector<pair<int, int> > > pa(m);
	for(int i = 0; i < m; i++)
	{
		path.clear();
		int a, b;
		cin >> a >> b;
		dfs(a, -1, b);
		for(int j = 0; j < path.size() - 1; j++)
		{
			pa[i].push_back({path[j], path[j + 1]});
		}
	}
	ll ans = 0;
	const int e = 1 << m;
	for(int i = 0; i < e; i++)
	{
		eg.assign(n, {});
		vis.assign(n, {});
		for(int j = 0; j < m; j++)
		{
			if((i >> j) & 1)
			{
				for(auto [x, y] : pa[j])
				{
					eg[x].push_back(y);
					eg[y].push_back(x);
				}
			}
		}
		ll val = 1;
		for(int j = 0; j < n - 1; j++)
		{
			if(!vis[j])
			{
				con(j);
				val *= k;
				val %= MOD;
			}
		}
		if(__builtin_popcount(i) % 2 == 0) ans += val;
		else ans -= val;
		ans %= MOD;
	}
	cout << (ans + MOD) % MOD;
}

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