oj.uz

Submission #916727

# Submission time Handle Problem Language Result Execution time Memory
916727 2024-01-26T11:57:47 Z penguin133 Paths (BOI18_paths) C++17
100 / 100
 413 ms 74368 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int A[300005];
vector <int> adj[300005];
vector < vector <int> > memo;
int dp(int x, int bm){
	if(memo[x][bm] != -1)return memo[x][bm];
	int ans = 1;
	for(auto i : adj[x])if(bm >> A[i] & 1)ans += dp(i, bm ^ (1 << A[i]));
	return memo[x][bm] = ans;
}

void solve(){
	int n, m, k; cin >> n >> m >> k;
	for(int i=1;i<=n;i++){
		cin >> A[i];
		A[i]--;
	}
	while(m--){
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	memo.resize(n + 1);
	for(int i = 0; i <= n; i++){
		memo[i].resize(1 << k);
		for(int j = 0; j < (1 << k); j++)memo[i][j] = -1;
	}
	int ans = 0;
	for(int i=1;i<=n;i++)ans += dp(i, ((1 << k) - 1) ^ (1 << A[i]));
	cout << ans - n << '\n';
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

paths.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main(){
      | ^~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8808 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 18768 KB Output is correct
2 Correct 48 ms 18260 KB Output is correct
3 Correct 280 ms 55372 KB Output is correct
4 Correct 99 ms 21472 KB Output is correct
5 Correct 63 ms 21076 KB Output is correct
6 Correct 200 ms 42360 KB Output is correct
7 Correct 314 ms 55192 KB Output is correct
8 Correct 285 ms 55696 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8808 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct
11 Correct 78 ms 18768 KB Output is correct
12 Correct 48 ms 18260 KB Output is correct
13 Correct 280 ms 55372 KB Output is correct
14 Correct 99 ms 21472 KB Output is correct
15 Correct 63 ms 21076 KB Output is correct
16 Correct 200 ms 42360 KB Output is correct
17 Correct 314 ms 55192 KB Output is correct
18 Correct 285 ms 55696 KB Output is correct
19 Correct 78 ms 18772 KB Output is correct
20 Correct 47 ms 18260 KB Output is correct
21 Correct 293 ms 55380 KB Output is correct
22 Correct 73 ms 21588 KB Output is correct
23 Correct 83 ms 20988 KB Output is correct
24 Correct 201 ms 42208 KB Output is correct
25 Correct 286 ms 55124 KB Output is correct
26 Correct 283 ms 55780 KB Output is correct
27 Correct 64 ms 18004 KB Output is correct
28 Correct 79 ms 20904 KB Output is correct
29 Correct 413 ms 74368 KB Output is correct
30 Correct 257 ms 46264 KB Output is correct
31 Correct 320 ms 46280 KB Output is correct
32 Correct 404 ms 74196 KB Output is correct
33 Correct 2 ms 8796 KB Output is correct
34 Correct 3 ms 8872 KB Output is correct
35 Correct 2 ms 8796 KB Output is correct
36 Correct 2 ms 8796 KB Output is correct
37 Correct 4 ms 8796 KB Output is correct
38 Correct 2 ms 8852 KB Output is correct
39 Correct 2 ms 8796 KB Output is correct
40 Correct 2 ms 8796 KB Output is correct
41 Correct 2 ms 8796 KB Output is correct
42 Correct 2 ms 8796 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 31 ms 11576 KB Output is correct
3 Correct 17 ms 11612 KB Output is correct
4 Correct 63 ms 23632 KB Output is correct
5 Correct 53 ms 24324 KB Output is correct
6 Correct 101 ms 42676 KB Output is correct
7 Correct 22 ms 11608 KB Output is correct
8 Correct 84 ms 30144 KB Output is correct
9 Correct 59 ms 30404 KB Output is correct
10 Correct 94 ms 30400 KB Output is correct
11 Correct 94 ms 27080 KB Output is correct
12 Correct 98 ms 35008 KB Output is correct
13 Correct 70 ms 27068 KB Output is correct
14 Correct 132 ms 42676 KB Output is correct
15 Correct 95 ms 42576 KB Output is correct
16 Correct 2 ms 8792 KB Output is correct
17 Correct 2 ms 8796 KB Output is correct
18 Correct 2 ms 8796 KB Output is correct
19 Correct 3 ms 8796 KB Output is correct
20 Correct 2 ms 8796 KB Output is correct
21 Correct 2 ms 8792 KB Output is correct
22 Correct 2 ms 8796 KB Output is correct
23 Correct 2 ms 8796 KB Output is correct
24 Correct 2 ms 8796 KB Output is correct
25 Correct 2 ms 8796 KB Output is correct