Submission #63070

#	Time	Username	Problem	Language	Result	Execution time	Memory
63070		zetapi	Paths (BOI18_paths)	C++14	100 / 100	752 ms	113824 KiB

paths

#include <bits/stdc++.h>
using namespace std;

#define pb  push_back
#define mp  make_pair
#define int long long
#define itr ::iterator 

typedef pair<int,int>  pii;

const int MAX=1e6;

pii edge[MAX];

int N,M,K,res,arr[MAX],dp[MAX][40];

signed main()
{
	ios_base::sync_with_stdio(false);
	
	cin>>N>>M>>K;
	for(int A=0;A<N;A++)
	{
		cin>>arr[A];
		arr[A]--;
	}
	for(int A=0;A<M;A++)
	{
		cin>>edge[A].first>>edge[A].second;
		edge[A].first--;
		edge[A].second--;
	}
	for(int A=0;A<N;A++)
		dp[A][(1<<arr[A])]=1;
	for(int A=2;A<=K;A++)
	{
		int u,v;
		for(int B=0;B<M;B++)
		{
			u=edge[B].first;
			v=edge[B].second;
			for(int C=0;C<(1<<K);C++)
			{
				if(((C&(1<<arr[v]))!=0) or __builtin_popcount(C)!=A-1)
					continue;
				dp[v][C|(1<<arr[v])]+=dp[u][C];
			}
			for(int C=0;C<(1<<K);C++)
			{
				if(((C&(1<<arr[u]))!=0) or __builtin_popcount(C)!=A-1)
					continue;
				dp[u][C|(1<<arr[u])]+=dp[v][C];
			}
		}

	}
	for(int A=0;A<N;A++)
		for(int B=0;B<(1<<K);B++)
			res+=dp[A][B];
	cout<<res-N;
	return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30