Submission #825436

#	Time	Username	Problem	Language	Result	Execution time	Memory
825436		QwertyPi	Paths (BOI18_paths)	C++14	100 / 100	737 ms	100424 KiB

paths

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

const int MAXN = 3e5 + 11;

int a[MAXN];
int dp[MAXN][1 << 5];
vector<int> G[MAXN];
struct edge{
	int u, v;
};

vector<edge> E;
int32_t main(){
	int n, m, k; cin >> n >> m >> k;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) a[i]--;
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v; u--; v--;
		G[u].push_back(v); G[v].push_back(u);
	}
	for(int i = 0; i < n; i++){
		dp[i][1 << a[i]] = 1;
	}

	for(int mask = 0; mask < (1 << k); mask++){
		for(int j = 0; j < k; j++){
			if((1 << j) & mask){
				for(int i = 0; i < n; i++){
					for(auto u : G[i]){
						if(a[u] != j) continue;
						dp[u][mask] += dp[i][mask - (1 << j)];
					}
				}
			}
		}
	}

	int ans = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < (1 << k); j++){
			ans += dp[i][j];
		}
	}
	cout << ans - n << endl;
}

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