Submission #85938

#	Time	Username	Problem	Language	Result	Execution time	Memory
85938		shoemakerjo	Paths (BOI18_paths)	C++14	100 / 100	528 ms	173540 KiB

paths

#include <bits/stdc++.h>

using namespace std;
#define ll long long

#define maxn 300010
ll dp[maxn][32];
ll ans = 0LL;

vector<int> adj[maxn];
int N, M, K;
int col[maxn];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		cin >> col[i];
		col[i]--;
	}
	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	for (int mask = 0; mask < (1 << K); mask++) {
		// cout << "on mask: " << mask << endl;

		for (int i = 1; i <= N; i++) {
			if ( (mask & (1 << col[i])) == 0 ) 
				continue;
			int gm = mask - ( 1 << col[i]);
			if (gm == 0) {
				dp[i][mask] = 1;
			}
			else {
				for (int v : adj[i]) {
					dp[i][mask] += dp[v][gm];
				}
			}
			ans += dp[i][mask];
		}
	}
	cout << ans-N << endl;
}

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