oj.uz

Submission #430784

# Submission time Handle Problem Language Result Execution time Memory
430784 2021-06-17T05:03:53 Z wind_reaper Paths (BOI18_paths) C++17
0 / 100
 800 ms 7112 KB 
#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 = 10001;

//***************** 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

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
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 800 ms 7112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -