oj.uz

Submission #430792

# Submission time Handle Problem Language Result Execution time Memory
430792 2021-06-17T05:11:01 Z wind_reaper Paths (BOI18_paths) C++17
23 / 100
 3000 ms 11848 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 = 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

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

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3404 KB Output is correct
2 Correct 4 ms 3452 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 4 ms 3404 KB Output is correct
7 Correct 4 ms 3404 KB Output is correct
8 Correct 5 ms 3452 KB Output is correct
9 Correct 5 ms 3404 KB Output is correct
10 Correct 3 ms 3404 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 7108 KB Output is correct
2 Correct 144 ms 7108 KB Output is correct
3 Runtime error 27 ms 6332 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3404 KB Output is correct
2 Correct 4 ms 3452 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 4 ms 3404 KB Output is correct
7 Correct 4 ms 3404 KB Output is correct
8 Correct 5 ms 3452 KB Output is correct
9 Correct 5 ms 3404 KB Output is correct
10 Correct 3 ms 3404 KB Output is correct
11 Correct 216 ms 7108 KB Output is correct
12 Correct 144 ms 7108 KB Output is correct
13 Runtime error 27 ms 6332 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3404 KB Output is correct
2 Correct 523 ms 4576 KB Output is correct
3 Correct 47 ms 4556 KB Output is correct
4 Correct 302 ms 9988 KB Output is correct
5 Correct 249 ms 11848 KB Output is correct
6 Execution timed out 3082 ms 9208 KB Time limit exceeded
7 Halted 0 ms 0 KB -