Submission #430792

#	Time	Username	Problem	Language	Result	Execution time	Memory
430792		wind_reaper	Paths (BOI18_paths)	C++17	23 / 100	3082 ms	11848 KiB

paths

#include <bits/stdc++.h>
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
*/

using namespace std;
// using namespace __gnu_pbds;
using namespace chrono;

// mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
/*
template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

//***************** CONSTANTS *****************

const int MXN = 100001;

//***************** GLOBAL VARIABLES *****************

int N, M, K;
vector<int> g[MXN];
int color[MXN];
int64_t dp[MXN];

//***************** AUXILIARY STRUCTS *****************



//***************** MAIN BODY *****************

int64_t process(int mask){
	vector<int> col;
	for(int i = 0; i < K; i++)
		if((mask >> i) & 1)
			col.push_back(i+1);

	assert(col.size() >= 2);

	int64_t ans = 0;

	do{
		memset(dp, 0, sizeof dp);
		set<int> s[2];

		for(int i = 1; i <= N; i++)
			if(color[i] == col[0]){
				dp[i] = 1;
				s[0].insert(i);
			}

		for(int idx = 1; idx < col.size(); idx++){
			int t = (idx & 1);
			int o = t ^ 1;

			for(int u : s[o])
				for(int v : g[u]){
					if(color[v] == col[idx]){
						dp[v] += dp[u];
						s[t].insert(v);
					}
				}

			s[o].clear();
		}

		for(int i = 1; i <= N; i++)
			if(color[i] == col.back())
				ans += dp[i];

	}while(next_permutation(col.begin(), col.end()));

	return ans;
}

void solve(){
	cin >> N >> M >> K;

	for(int i = 1; i <= N; i++)
		cin >> color[i];

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

	// for(int i = 1; i <= N; i++)
	// 	g[0].push_back(i);

	int64_t ans = 0;

	for(int mask = 0; mask < (1 << K); mask++){
		if(__builtin_popcount(mask) >= 2)
			ans += process(mask);
	}

	cout << ans << '\n';
}

//***************** *****************

int32_t main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);

	#ifdef LOCAL
		auto begin = high_resolution_clock::now();
	#endif

	int tc = 1;
	// cin >> tc; 
	for (int t = 0; t < tc; t++)
		solve();

	#ifdef LOCAL 
		auto end = high_resolution_clock::now();
		cout << fixed << setprecision(4);
		cout << "Execution Time: " << duration_cast<duration<double>>(end - begin).count() << "seconds" << endl;
	#endif

	return 0;
}

/*
If code gives a WA, check for the following : 
1. I/O format

2. Are you clearing all global variables in between tests if multitests are a thing

3. Can you definitively prove the logic
*/

Compilation message (stderr)

paths.cpp: In function 'int64_t process(int)':
paths.cpp:53:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int idx = 1; idx < col.size(); idx++){
      |                    ~~~~^~~~~~~~~~~~

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