Submission #1197475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197475		qrn	Paths (BOI18_paths)	C++20	100 / 100	548 ms	132140 KiB

paths

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

#define pb push_back
#define ins insert
#define fi first
#define se second
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 9973;
const intt inf = 1e18;
const intt mxN = 400005;
const intt L = 21;

vector<vector<intt>> graph;
vector<intt> color(mxN);

void solve() {
	intt N, M, K;
	cin >> N >> M >> K;
	graph.assign(N + 1, vector<intt> {});

	for(intt i = 1; i <= N; i++) {
		intt x;
		cin >> x;
		color[i] = x-1;
	}

	for(intt i = 1; i <= M; i++) {
		intt a, b;
		cin >> a >> b;
		graph[a].pb(b);
		graph[b].pb(a);;
	}

	vector<vector<intt>> dp(N + 1, vector<intt> ((1 << 5) + 10, 0ll));

	for(intt node = 1; node <= N; node++) dp[node][1 << color[node]] = 1;

	for(intt mask = 0; mask < (1 << K); mask++) {
		for(intt node = 1; node <= N; node++) {
			for(auto u : graph[node]) {
				if((1 << color[u]) & mask)
				dp[node][mask] += dp[u][(mask ^ (1 << color[node]))];
			}
		}		
	}

	intt ans = 0;
	for(intt node = 1; node <= N; node++) {
		// cout << node << ": ";
		for(intt mask = 0; mask < (1 << 5); mask++) {
			if(__builtin_popcount(mask) > 1) {
				ans += dp[node][mask];
			}
			// cout << mask << " : " << dp[node][mask] << endl;
		}
		// cout << endl << endl;
	}
	cout << ans << endl;
}


signed main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(NULL);                
	cout.tie(NULL);
	intt tst = 1, idx = 1;
	// cin >> tst;
	while(tst--) {
		// cout << "Case " << idx << ":" << endl; 
		solve();
		// idx++;
	}
}

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