Submission #595422

#	Time	Username	Problem	Language	Result	Execution time	Memory
595422		UncoolAnon	Paths (BOI18_paths)	C++14	100 / 100	407 ms	64612 KiB

paths

//18:08
#include <bits/stdc++.h> 
#define int long long 
using namespace std; 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr); 
	int n,m,k; 
	cin>>n>>m>>k; 
	vector<int> adj[n+1],color(n+1); 
	for(int i=1;i<=n;i++) cin>>color[i],color[i]--; 
	while(m--){
		int a,b; 
		cin>>a>>b; 
		adj[a].push_back(b); 
		adj[b].push_back(a); 
	}
	int B=(1LL<<k); 
	vector<vector<int>> dp(B,vector<int>(n+1,-1)); 
	for(auto&x:dp) for(int&y:x) y=-1; 
	function<int(int,int)> dfs=[&](int mask,int a){
		if(dp[mask][a]!=-1) return dp[mask][a];
		int answer=1; 
		for(int&x:adj[a]){
			if(((1LL<<color[x])&mask)==0){
				answer+=dfs((1LL<<color[x])|mask,x); 
			}
		}
		return dp[mask][a]=answer; 
	}; 
	int answer=0; 
	for(int i=1;i<=n;i++) answer+=dfs((1LL<<color[i]),i); 
	cout<<answer-n; 
	return 0;
}

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