Submission #858536

#	Time	Username	Problem	Language	Result	Execution time	Memory
858536		serifefedartar	Paths (BOI18_paths)	C++17	100 / 100	382 ms	59708 KiB

paths

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 18; 
const ll INF = 1e15;
const ll MAXN = 3e5 + 5;

vector<vector<int>> graph;
int t[MAXN], dp[MAXN][32];

int main() {
	fast
	int N, M, K, a, b;
	cin >> N >> M >> K;

	graph = vector<vector<int>>(N+1, vector<int>());
	for (int i = 1; i <= N; i++) {
		cin >> t[i], t[i]--;
		for (int msk = 0; msk < 32; msk++)
			dp[i][msk] = 0;
		dp[i][1<<t[i]] = 1;
	}
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	for (int cnt = 2; cnt <= K; cnt++) {
		for (int msk = 0; msk < 32; msk++) {
			if (__builtin_popcount(msk) != cnt)
				continue;

			for (int node = 1; node <= N; node++) {
				int m = 1<<t[node];
				if ((m & msk) == 0)
					continue;
				for (auto u : graph[node])
					dp[node][msk] += dp[u][msk ^ m];
			}
		}
	}
		
	ll ans = 0;
	for (int i = 1; i <= N; i++) {
		for (int msk = 0; msk < 32; msk++)
			ans += dp[i][msk];
	}
	cout << ans - N << "\n";
}

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