oj.uz

Submission #975651

# Submission time Handle Problem Language Result Execution time Memory
975651 2024-05-05T16:02:07 Z Isam Paths (BOI18_paths) C++17
53 / 100
 98 ms 65112 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define eb emplace_back
#define int long long

constexpr int sz = 2e5 + 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 16 ms 57948 KB Output is correct
2 Correct 9 ms 57944 KB Output is correct
3 Correct 8 ms 57948 KB Output is correct
4 Correct 8 ms 57948 KB Output is correct
5 Correct 9 ms 57948 KB Output is correct
6 Correct 8 ms 58084 KB Output is correct
7 Correct 8 ms 57948 KB Output is correct
8 Correct 8 ms 57944 KB Output is correct
9 Correct 8 ms 57948 KB Output is correct
10 Correct 8 ms 58068 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 65108 KB Output is correct
2 Correct 58 ms 65112 KB Output is correct
3 Incorrect 16 ms 58384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 57948 KB Output is correct
2 Correct 9 ms 57944 KB Output is correct
3 Correct 8 ms 57948 KB Output is correct
4 Correct 8 ms 57948 KB Output is correct
5 Correct 9 ms 57948 KB Output is correct
6 Correct 8 ms 58084 KB Output is correct
7 Correct 8 ms 57948 KB Output is correct
8 Correct 8 ms 57944 KB Output is correct
9 Correct 8 ms 57948 KB Output is correct
10 Correct 8 ms 58068 KB Output is correct
11 Correct 69 ms 65108 KB Output is correct
12 Correct 58 ms 65112 KB Output is correct
13 Incorrect 16 ms 58384 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 57948 KB Output is correct
2 Correct 46 ms 60256 KB Output is correct
3 Correct 25 ms 60252 KB Output is correct
4 Correct 59 ms 61520 KB Output is correct
5 Correct 49 ms 61896 KB Output is correct
6 Correct 86 ms 61528 KB Output is correct
7 Correct 32 ms 60248 KB Output is correct
8 Correct 74 ms 61592 KB Output is correct
9 Correct 59 ms 61892 KB Output is correct
10 Correct 71 ms 61644 KB Output is correct
11 Correct 74 ms 60628 KB Output is correct
12 Correct 67 ms 60988 KB Output is correct
13 Correct 76 ms 60748 KB Output is correct
14 Correct 98 ms 61464 KB Output is correct
15 Correct 77 ms 61532 KB Output is correct
16 Correct 8 ms 57948 KB Output is correct
17 Correct 8 ms 57948 KB Output is correct
18 Correct 8 ms 57948 KB Output is correct
19 Correct 8 ms 57948 KB Output is correct
20 Correct 8 ms 57948 KB Output is correct
21 Correct 8 ms 57948 KB Output is correct
22 Correct 8 ms 57948 KB Output is correct
23 Correct 8 ms 57948 KB Output is correct
24 Correct 8 ms 57948 KB Output is correct
25 Correct 8 ms 57948 KB Output is correct