Submission #160283

#	Time	Username	Problem	Language	Result	Execution time	Memory
160283		pamaj	Paths (BOI18_paths)	C++14	100 / 100	563 ms	173560 KiB

paths

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
typedef long long ll;
int n, m, k;
int cor[maxn];
int dp[maxn][129];
bool vis[maxn];
 
vector<int> G[maxn];
 
 
inline ll dfs(int x, int mask)
{
	//if(mask == (1 << (k + 1)) - 1) return 1;
	
	if(dp[x][mask] != -1) return dp[x][mask];
	
	ll cont = 0;
	
	for(auto u : G[x])
	{	
		if((mask & (1 << cor[u])) == 0) 
		{
			cont += 1 + dfs(u, (mask | (1 << cor[u])));
		}
 
		//cont += dfs(u, (1 << cor[u]));
	}
 
	return dp[x][mask] = cont;
 
}
 
int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr);
	
	cin >> n >> m >> k;
 
	for(int i = 1; i <= n; i++)
		cin >> cor[i];
 
	for(int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	memset(dp, -1, sizeof(dp));
 
	ll ans = 0;
	for(int i = 1; i <= n; i++)
	{	
		ans += dfs(i, 1 << cor[i]);
	}
	cout << ans << "\n";
 
}

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