Submission #1098066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098066		Alihan_8	Paths (BOI18_paths)	C++17	100 / 100	217 ms	70740 KiB

paths

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

using i64 = long long;

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m, k; cin >> n >> m >> k;
	
	vector <int> c(n);
	
	for ( auto &u: c ){
		cin >> u; --u;
	}
	
	vector <vector<int>> adj(n);
	
	for ( int i = 0; i < m; i++ ){
		int u, v; cin >> u >> v;
		
		--u, --v;
		
		adj[u].pb(v);
		adj[v].pb(u);
	}
	
	const int S = 1 << k;
	
	vector <vector<i64>> dp(n, vector <i64> (S, -1));
	
	auto dfs = [&](auto dfs, int u, int mask) -> i64{
		if ( dp[u][mask] != -1 ) return dp[u][mask];
		
		i64 &ret = dp[u][mask]; ret = 0;
		
		for ( auto &v: adj[u] ){
			if ( mask >> c[v] & 1 ) continue;
			
			ret += dfs(dfs, v, mask | (1 << c[v])) + 1;
		}
		
		return ret;
	};
	
	i64 ans = 0;
	
	for ( int i = 0; i < n; i++ ){
		ans += dfs(dfs, i, 1 << c[i]);
	}
	
	cout << ans;
	
	cout << '\n';
}

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