제출 #391125

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391125		nikatamliani	Paths (BOI18_paths)	C++14	100 / 100	406 ms	56772 KiB

paths

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 3e5+10;
int a[N], color[N], n, m, k;
vector<int> edges[N];
long long dp[32][N];
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	for(int i = 0; i < n; ++i) {
		cin >> color[i];
		--color[i];
	}
	for(int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		--u, --v;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	for(int i = 0; i < n; ++i) {
		dp[1 << color[i]][i] = 1;
	}
	for(int mask = 1; mask < (1 << k); ++mask) {
		for(int x = 0; x < n; ++x) {
			int bit = color[x];
			if(mask >> bit & 1) {
				int submask = mask ^ (1 << bit);
				for(int i : edges[x]) {
					dp[mask][x] += dp[submask][i];
				}
			}
		}
	}
	long long ans = -n;
	for(int mask = 0; mask < (1 << k); ++mask) {
		for(int x = 0; x < n; ++x) {
			ans += dp[mask][x];
		}
	}
	cout << ans << endl;
}

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