Submission #760198

#	Time	Username	Problem	Language	Result	Execution time	Memory
760198		MetalPower	Paths (BOI18_paths)	C++14	100 / 100	457 ms	99532 KiB

paths

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MX = 3e5 + 10;
const int MK = 33;

int N, M, K, col[MX];
vector<int> adj[MX];
ll dp[MX][MK];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> M >> K;
	for(int i = 1; i <= N; i++){
		cin >> col[i]; col[i]--;
	}

	for(int i = 1; i <= M; i++){
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for(int i = 1; i <= N; i++) dp[i][1 << col[i]] = 1;

	int mx = 1 << K;
	for(int mask = 1; mask < mx; mask++){
		for(int i = 1; i <= N; i++){
			for(int nx : adj[i]){
				if((mask >> col[nx] & 1) == 0) dp[nx][mask | 1 << col[nx]] += dp[i][mask];
			}
		}
	}

	ll ans = 0;
	for(int i = 1; i <= N; i++){
		for(int mask = 0; mask < mx; mask++) ans += dp[i][mask];
	}
	cout << ans - N << '\n';
}

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