Submission #307090

#	Time	Username	Problem	Language	Result	Execution time	Memory
307090		Rainbowbunny	Paths (BOI18_paths)	C++17	100 / 100	1158 ms	97272 KiB

paths

#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
using namespace std;
using cd = complex <double>;
 
typedef pair <int, int> pii;
const int N = 3e3 + 5;
const long long INF = 1e18;
const int mod = 998244353;//786433;//998244353;
const double Pi = acos(-1);
 
 
void Fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}
 
int n, m, k;
int c[300005];
long long dp[300005][32];
vector <int> Adj[300005];
 
int main()
{
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++)
	{
		cin >> c[i];
		c[i]--;
		dp[i][1 << c[i]] = 1;
	}
	for(int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		Adj[u].eb(v);
		Adj[v].eb(u);
	}
	for(int i = 2; i <= k; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			for(int t = 1; t <= 31; t++)
			{
				if(__builtin_popcount(t) != i - 1)
				{
					continue;
				}
				
				for(auto x : Adj[j])
				{
					if((t & (1 << c[x])) == 0)
					{
						dp[x][t ^ (1 << c[x])] += dp[j][t];
					}
				}
			}
		}
	}
	long long ans = 0;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= 31; j++)
		{
			ans += dp[i][j];
		}
	}
	cout << ans - (long long)n;
}

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