oj.uz

Submission #975654

# Submission time Handle Problem Language Result Execution time Memory
975654 2024-05-05T16:16:10 Z Isam Paths (BOI18_paths) C++17
100 / 100
 355 ms 102740 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define eb emplace_back
#define int long long

constexpr int sz = 3e5 + 5;
 
int n, m, k, ans, c[sz];
 
vector<int> g[sz];

int dp[sz][33];

int dfs(int node, int co){
	
	if(dp[node][co] != -1) return dp[node][co];
	
	dp[node][co] = (__builtin_popcount(co) > 1);
	
	for(auto &to : g[node]){
		if(co & (1 << c[to])) continue;
		
		
		dp[to][co | (1 << c[to])] = dfs(to, co | (1 << c[to]));
		
		
	}
	
	for(auto &to : g[node]){
		
		if(~co & (1 << c[to])) dp[node][co] += dp[to][co | (1 << c[to])];
		
	}
	
	return dp[node][co];	
}
 
 
 
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	
	cin >> n >> m >> k;
	
	for(register int i = 1; i <= n; ++i){
		cin >> c[i];
	//	c[i]--;
	}
	
	for(register int i = 1, u, v; i <= m; ++i){
		cin >> u >> v;
		g[u].eb(v), g[v].eb(u);
	}
	
	memset(dp, -1, sizeof(dp));
	
	for(register int i = 1; i <= n; ++i){
		dp[i][1 << c[i]] = dfs(i, (1 << c[i]));
		ans += dp[i][1 << c[i]];
	}
	
	cout << ans << '\n';
	
	
	return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:46:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   46 |  for(register int i = 1; i <= n; ++i){
      |                   ^
paths.cpp:51:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   51 |  for(register int i = 1, u, v; i <= m; ++i){
      |                   ^
paths.cpp:51:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   51 |  for(register int i = 1, u, v; i <= m; ++i){
      |                          ^
paths.cpp:51:29: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   51 |  for(register int i = 1, u, v; i <= m; ++i){
      |                             ^
paths.cpp:58:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   58 |  for(register int i = 1; i <= n; ++i){
      |                   ^

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 86620 KB Output is correct
2 Correct 12 ms 86620 KB Output is correct
3 Correct 12 ms 86740 KB Output is correct
4 Correct 12 ms 86620 KB Output is correct
5 Correct 12 ms 86620 KB Output is correct
6 Correct 13 ms 86620 KB Output is correct
7 Correct 13 ms 86772 KB Output is correct
8 Correct 12 ms 86620 KB Output is correct
9 Correct 11 ms 86616 KB Output is correct
10 Correct 15 ms 86620 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 93832 KB Output is correct
2 Correct 63 ms 93776 KB Output is correct
3 Correct 280 ms 101524 KB Output is correct
4 Correct 99 ms 98244 KB Output is correct
5 Correct 74 ms 98048 KB Output is correct
6 Correct 182 ms 99724 KB Output is correct
7 Correct 274 ms 102544 KB Output is correct
8 Correct 253 ms 102740 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 86620 KB Output is correct
2 Correct 12 ms 86620 KB Output is correct
3 Correct 12 ms 86740 KB Output is correct
4 Correct 12 ms 86620 KB Output is correct
5 Correct 12 ms 86620 KB Output is correct
6 Correct 13 ms 86620 KB Output is correct
7 Correct 13 ms 86772 KB Output is correct
8 Correct 12 ms 86620 KB Output is correct
9 Correct 11 ms 86616 KB Output is correct
10 Correct 15 ms 86620 KB Output is correct
11 Correct 73 ms 93832 KB Output is correct
12 Correct 63 ms 93776 KB Output is correct
13 Correct 280 ms 101524 KB Output is correct
14 Correct 99 ms 98244 KB Output is correct
15 Correct 74 ms 98048 KB Output is correct
16 Correct 182 ms 99724 KB Output is correct
17 Correct 274 ms 102544 KB Output is correct
18 Correct 253 ms 102740 KB Output is correct
19 Correct 75 ms 96752 KB Output is correct
20 Correct 61 ms 96084 KB Output is correct
21 Correct 298 ms 102328 KB Output is correct
22 Correct 84 ms 98128 KB Output is correct
23 Correct 74 ms 98280 KB Output is correct
24 Correct 201 ms 99752 KB Output is correct
25 Correct 254 ms 102328 KB Output is correct
26 Correct 263 ms 102740 KB Output is correct
27 Correct 84 ms 95940 KB Output is correct
28 Correct 107 ms 98132 KB Output is correct
29 Correct 345 ms 102224 KB Output is correct
30 Correct 285 ms 99464 KB Output is correct
31 Correct 355 ms 99520 KB Output is correct
32 Correct 315 ms 102228 KB Output is correct
33 Correct 12 ms 86616 KB Output is correct
34 Correct 12 ms 86620 KB Output is correct
35 Correct 12 ms 86832 KB Output is correct
36 Correct 12 ms 86620 KB Output is correct
37 Correct 11 ms 86620 KB Output is correct
38 Correct 12 ms 86616 KB Output is correct
39 Correct 12 ms 86616 KB Output is correct
40 Correct 11 ms 86620 KB Output is correct
41 Correct 12 ms 86620 KB Output is correct
42 Correct 12 ms 86620 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 86620 KB Output is correct
2 Correct 50 ms 88924 KB Output is correct
3 Correct 29 ms 88916 KB Output is correct
4 Correct 63 ms 90316 KB Output is correct
5 Correct 64 ms 90844 KB Output is correct
6 Correct 103 ms 90188 KB Output is correct
7 Correct 36 ms 88920 KB Output is correct
8 Correct 78 ms 90320 KB Output is correct
9 Correct 69 ms 90568 KB Output is correct
10 Correct 97 ms 90320 KB Output is correct
11 Correct 73 ms 89264 KB Output is correct
12 Correct 65 ms 89932 KB Output is correct
13 Correct 74 ms 89420 KB Output is correct
14 Correct 113 ms 90476 KB Output is correct
15 Correct 99 ms 90408 KB Output is correct
16 Correct 13 ms 86624 KB Output is correct
17 Correct 11 ms 86620 KB Output is correct
18 Correct 12 ms 86800 KB Output is correct
19 Correct 12 ms 86620 KB Output is correct
20 Correct 11 ms 86724 KB Output is correct
21 Correct 13 ms 86620 KB Output is correct
22 Correct 12 ms 86620 KB Output is correct
23 Correct 12 ms 86616 KB Output is correct
24 Correct 11 ms 86620 KB Output is correct
25 Correct 12 ms 86620 KB Output is correct