Submission #331065

#	Time	Username	Problem	Language	Result	Execution time	Memory
331065		nandonathaniel	Paths (BOI18_paths)	C++14	100 / 100	535 ms	97388 KiB

paths

#include<bits/stdc++.h>
using namespace std;
const int MAXN=300005,LOG=5;
long long dp[MAXN][1<<LOG];

vector<int> adj[MAXN];
int c[MAXN];

long long DP(int now,int mask){
	long long &ret=dp[now][mask];
	if(ret!=-1)return ret;
	ret=1;
	for(auto nxt : adj[now]){
		if(mask & (1<<c[nxt]))continue;
		ret+=DP(nxt,mask+(1<<c[nxt]));
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,m,k,u,v;
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++){
		cin >> c[i];
		c[i]--;
	}
	for(int i=1;i<=m;i++){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	memset(dp,-1,sizeof(dp));
	long long ans=-n;
	for(int i=1;i<=n;i++){
		ans+=DP(i,1<<c[i]);
	}
	cout << ans << '\n';
	return 0;
}

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