oj.uz

답안 #430789

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
430789 2021-06-17T05:07:01 Z wind_reaper Paths (BOI18_paths) C++17
23 / 100
 523 ms 6480 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
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 4388 KB Output is correct
2 Correct 151 ms 6480 KB Output is correct
3 Runtime error 6 ms 1344 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 1 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 213 ms 4388 KB Output is correct
12 Correct 151 ms 6480 KB Output is correct
13 Runtime error 6 ms 1344 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 523 ms 2480 KB Output is correct
3 Correct 53 ms 2472 KB Output is correct
4 Runtime error 7 ms 1348 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -