Submission #1130637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130637		Muhammet	Paths (BOI18_paths)	C++20	100 / 100	389 ms	103924 KiB

paths

#include "bits/stdc++.h"

using namespace std;

#define ll long long

int n, m, k;

ll ans = 0;

vector <int> a;

vector <vector <ll>> dp;

vector <vector <int>> v;

ll f(int x, int mask){
	if(~dp[x][mask]) return dp[x][mask];
	ll k = 1;
	for(auto i : v[x]){
		if((mask&(1<<a[i])) == 0){
			k += f(i,(mask|(1<<a[i])));
		}
	}
	return dp[x][mask] = k;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> m >> k;
	dp.assign(n+1, vector <ll> (1<<k+1,-1));
	v.resize(n+1), a.resize(n+1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i]--;
	}
	for(int i = 1; i <= m; i++){
		int u1, u2;
		cin >> u1 >> u2;
		v[u1].push_back(u2);
		v[u2].push_back(u1);
	}
	for(int i = 1; i <= n; i++){
		ans += f(i,(1<<a[i]));
	}
	cout << ans-n << '\n';
}

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