제출 #1300930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1300930		MuhammadSaram	Šarenlist (COCI22_sarenlist)	C++20	110 / 110	5 ms	588 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 1e9 + 7, M = 61;

int dep[M], par[M];
vector<int> nei[M];

void dfs(int u)
{
	for (int i:nei[u])
		if (i!=par[u])
			par[i]=u, dep[i]=dep[u]+1, dfs(i);
}

int lca(int u,int v)
{
	if (dep[u]>dep[v]) swap(u,v);
	while (dep[v]>dep[u]) v=par[v];
	while (u!=v)
		u=par[u], v=par[v];
	return u;
}

signed main()
{
	int n,m,k;
	cin>>n>>m>>k;
	int ans=1, pw[n];pw[0]=1;
	for (int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		nei[u].push_back(v);
		nei[v].push_back(u);
		ans=ans*k%mod, pw[i]=ans;
	}
	dfs(1);
	int msk[m]={};
	for (int i=0;i<m;i++)
	{
		int u,v;
		cin>>u>>v;
		int p=lca(u,v);
		while (u!=p)
			msk[i]|=(1ll<<u), u=par[u];
		while (v!=p)
			msk[i]|=(1ll<<v), v=par[v];
	}
	for (int ms=1;ms<(1<<m);ms++)
	{
		int y=ms, uni=0, now=1;
		while (y)
		{
			bool in=0;
			for (int p=0;p<m;p++)
				if (y>>p&1)
				{
					if (uni&msk[p]) uni|=msk[p], in=1, y-=(1<<p);
				}
			if (!in)
			{
				for (int p=0;p<m;p++)
					if (y>>p&1)
					{
						uni|=msk[p], now=now*k%mod;
						break;
					}
			}
		}
		int z=n-1-__builtin_popcountll(uni);
		ans+=pw[z]*now%mod;
		if (__builtin_popcount(ms)%2) ans-=2*pw[z]*now%mod;
		ans=(ans+mod*2)%mod;
	}
	cout<<ans<<endl;
	
	return 0;
}

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