oj.uz

Submission #636385

# Submission time Handle Problem Language Result Execution time Memory
636385 2022-08-29T03:31:04 Z TranGiaHuy1508 Paths (BOI18_paths) C++17
100 / 100
 745 ms 100304 KB 
/*
	Unknown's C++ Template (v3.2)
*/

#include "bits/stdc++.h"
using namespace std;

#define int long long

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
template <class T> using maxpq = priority_queue<T>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mid ((l+r)>>1)
#define fi first
#define se second

#ifdef LOCAL
	#define debug(x) cout << #x << " = " << x << "\n";
#else
	#define debug(x) ;
#endif

template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x)
{ out << "(" << x.first << ", " << x.second << ")"; return out; }

template <class T>
ostream& operator << (ostream& out, vector<T> x){
	out << "[";
	for (int i=0; i<sz(x); i++) { out << (i ? ", " : "") << x[i]; }
	out << "]"; return out;
}

template <class T>
istream& operator >> (istream& in, vector<T> &x){
	for (auto &i: x) in >> i;
	return in;
}

const ld PI = acos(-1.0);
const int allmod[3] = {(int)1e9+7, 998244353, (int)1e9+9};
const int mod = allmod[0];
const int maxn = 3e5 + 64;
const ll inf = 1e18;
const ld eps = 1e-6;
const int multitest = 0;

int n, m, k, cl[maxn], dp[maxn][32];
vvi adj;

void main_program(){
	cin >> n >> m >> k;

	for (int i = 0; i < n; i++){
		int c; cin >> c;
		cl[i] = c - 1; 
		dp[i][1 << (c - 1)] = 1;
	}

	adj.resize(n);
	for (int i = 0; i < m; i++){
		int a, b; cin >> a >> b;
		a--; b--;

		adj[a].pb(b);
		adj[b].pb(a);
	}

	for (int it = 1; it <= k; it++){
		for (int mask = 0; mask < (1 << k); mask++){
			if (__builtin_popcount(mask) != it) continue;
			for (int u = 0; u < n; u++){
				for (auto v: adj[u]){
					if ((mask >> cl[v]) & 1) continue;
					dp[v][mask | (1 << cl[v])] += dp[u][mask];
				}
			}
		}
	}

	int res = 0;
	for (int mask = 0; mask < (1 << k); mask++){
		if (__builtin_popcount(mask) > 1){
			for (int i = 0; i < n; i++) res += dp[i][mask];
		}
	}

	cout << res << "\n";
}

void pre_main(){

}

signed main(){
	#ifdef LOCAL
		auto stime = chrono::high_resolution_clock::now();
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#ifndef ONLINE_JUDGE
		if (fopen(".inp", "r")){
			freopen(".inp", "r", stdin);
			freopen(".out", "w", stdout);
		}
	#endif
	int t = 1; if (multitest) cin >> t;
	pre_main();
	while (t--) main_program();
	#ifdef LOCAL
		auto etime = chrono::high_resolution_clock::now();
		auto duration = chrono::duration_cast<chrono::milliseconds>(etime-stime).count();
		cout << "\n[" << duration << "ms]\n";
	#endif
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:112:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |    freopen(".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~
paths.cpp:113:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |    freopen(".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 11704 KB Output is correct
2 Correct 64 ms 9832 KB Output is correct
3 Correct 427 ms 99788 KB Output is correct
4 Correct 106 ms 20248 KB Output is correct
5 Correct 81 ms 20232 KB Output is correct
6 Correct 262 ms 69564 KB Output is correct
7 Correct 399 ms 99920 KB Output is correct
8 Correct 433 ms 100304 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 328 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 92 ms 11704 KB Output is correct
12 Correct 64 ms 9832 KB Output is correct
13 Correct 427 ms 99788 KB Output is correct
14 Correct 106 ms 20248 KB Output is correct
15 Correct 81 ms 20232 KB Output is correct
16 Correct 262 ms 69564 KB Output is correct
17 Correct 399 ms 99920 KB Output is correct
18 Correct 433 ms 100304 KB Output is correct
19 Correct 80 ms 11724 KB Output is correct
20 Correct 63 ms 9932 KB Output is correct
21 Correct 426 ms 99788 KB Output is correct
22 Correct 100 ms 20172 KB Output is correct
23 Correct 84 ms 20204 KB Output is correct
24 Correct 271 ms 69540 KB Output is correct
25 Correct 428 ms 99864 KB Output is correct
26 Correct 423 ms 100284 KB Output is correct
27 Correct 92 ms 9892 KB Output is correct
28 Correct 131 ms 14068 KB Output is correct
29 Correct 738 ms 99908 KB Output is correct
30 Correct 402 ms 55268 KB Output is correct
31 Correct 421 ms 55360 KB Output is correct
32 Correct 745 ms 99820 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 0 ms 332 KB Output is correct
39 Correct 0 ms 340 KB Output is correct
40 Correct 0 ms 340 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 212 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 328 KB Output is correct
2 Correct 50 ms 3368 KB Output is correct
3 Correct 21 ms 3328 KB Output is correct
4 Correct 102 ms 33308 KB Output is correct
5 Correct 71 ms 33672 KB Output is correct
6 Correct 305 ms 33300 KB Output is correct
7 Correct 31 ms 3284 KB Output is correct
8 Correct 156 ms 33268 KB Output is correct
9 Correct 99 ms 33728 KB Output is correct
10 Correct 129 ms 33940 KB Output is correct
11 Correct 147 ms 18112 KB Output is correct
12 Correct 149 ms 25916 KB Output is correct
13 Correct 146 ms 18460 KB Output is correct
14 Correct 288 ms 33312 KB Output is correct
15 Correct 275 ms 33356 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 328 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct