Submission #1175521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175521		xnqs	Paths (BOI18_paths)	C++20	100 / 100	195 ms	92720 KiB

paths

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>

int gs, edg, cols;
std::vector<std::vector<int>> adj_list;
int node_color[300005];
int64_t dp[300005][32];

int64_t sol(int node, int mask) {
	if (__builtin_popcount(mask)==cols) {
		return 1;
	}
	if (dp[node][mask]!=-1) {
		return dp[node][mask];
	}

	int64_t& ret = (dp[node][mask] = 1);
	for (const auto& i : adj_list[node]) {
		if (!(mask&(1<<node_color[i]))) {
			ret += sol(i, mask|(1<<node_color[i]));
		}
	}

	return ret;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> gs >> edg >> cols;
	for (int i = 1; i <= gs; i++) {
		std::cin >> node_color[i];
		--node_color[i];
	}

	adj_list.resize(gs+1);
	for (int i = 0, a, b; i < edg; i++) {
		std::cin >> a >> b;
		adj_list[a].emplace_back(b);
		adj_list[b].emplace_back(a);
	}

	int64_t ret = 0;
	memset(dp,-1,sizeof(dp));
	for (int i = 1; i <= gs; i++) {
		ret += sol(i, 1<<node_color[i]);
	}

	std::cout << ret - gs << "\n";
}

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