Submission #881097

#	Time	Username	Problem	Language	Result	Execution time	Memory
881097		OAleksa	Paths (BOI18_paths)	C++14	100 / 100	290 ms	100464 KiB

paths

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int maxn = 3e5 + 69;
int n, m, k, a[maxn], dp[maxn][1 << 5];
vector<int> g[maxn];
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
   int tt = 1;
  	//cin >> tt;
   while (tt--) {
   	cin >> n >> m >> k;
   	for (int i = 1;i <= n;i++) {
   		cin >> a[i];
   		--a[i];
   		dp[i][1 << a[i]] = 1;
   	}
   	for (int i = 1;i <= m;i++) {
   		int a, b;
   		cin >> a >> b;
   		g[a].push_back(b);
   		g[b].push_back(a);
   	}
   	for (int mask = 1;mask < (1 << k);mask++) {
   		int x = __builtin_popcount(mask);
   		if (x == 1)
   			continue;
   		for (int i = 1;i <= n;i++) {
   			if (mask & (1 << a[i])) {
   				for (auto u : g[i]) {
   					dp[i][mask] += dp[u][mask ^ (1 << a[i])];
   				}
   			}
   		}
   	}
   	int ans = 0;
   	for (int i = 1;i <= n;i++) {
   		for (int j = 0;j < (1 << k);j++)
   			ans += dp[i][j];
   	}
   	ans -= n;
   	cout << ans;
	}
	return 0;
}

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