oj.uz

Submission #975648

# Submission time Handle Problem Language Result Execution time Memory
975648 2024-05-05T15:59:10 Z Isam Paths (BOI18_paths) C++17
53 / 100
 92 ms 65132 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])) continue;
		
		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:47:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   47 |  for(register int i = 1; i <= n; ++i){
      |                   ^
paths.cpp:52:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   52 |  for(register int i = 1, u, v; i <= m; ++i){
      |                   ^
paths.cpp:52:26: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   52 |  for(register int i = 1, u, v; i <= m; ++i){
      |                          ^
paths.cpp:52:29: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   52 |  for(register int i = 1, u, v; i <= m; ++i){
      |                             ^
paths.cpp:59:19: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   59 |  for(register int i = 1; i <= n; ++i){
      |                   ^

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 57944 KB Output is correct
2 Correct 8 ms 57944 KB Output is correct
3 Correct 8 ms 58084 KB Output is correct
4 Correct 8 ms 57948 KB Output is correct
5 Correct 8 ms 58012 KB Output is correct
6 Correct 8 ms 57948 KB Output is correct
7 Correct 8 ms 57948 KB Output is correct
8 Correct 8 ms 57948 KB Output is correct
9 Correct 8 ms 57948 KB Output is correct
10 Correct 8 ms 57948 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 65132 KB Output is correct
2 Correct 56 ms 65132 KB Output is correct
3 Incorrect 15 ms 58204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 57944 KB Output is correct
2 Correct 8 ms 57944 KB Output is correct
3 Correct 8 ms 58084 KB Output is correct
4 Correct 8 ms 57948 KB Output is correct
5 Correct 8 ms 58012 KB Output is correct
6 Correct 8 ms 57948 KB Output is correct
7 Correct 8 ms 57948 KB Output is correct
8 Correct 8 ms 57948 KB Output is correct
9 Correct 8 ms 57948 KB Output is correct
10 Correct 8 ms 57948 KB Output is correct
11 Correct 68 ms 65132 KB Output is correct
12 Correct 56 ms 65132 KB Output is correct
13 Incorrect 15 ms 58204 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 8 ms 57944 KB Output is correct
2 Correct 45 ms 60252 KB Output is correct
3 Correct 25 ms 61024 KB Output is correct
4 Correct 61 ms 62804 KB Output is correct
5 Correct 59 ms 63684 KB Output is correct
6 Correct 92 ms 62932 KB Output is correct
7 Correct 32 ms 61000 KB Output is correct
8 Correct 73 ms 62812 KB Output is correct
9 Correct 59 ms 63292 KB Output is correct
10 Correct 70 ms 62924 KB Output is correct
11 Correct 76 ms 61640 KB Output is correct
12 Correct 61 ms 62312 KB Output is correct
13 Correct 80 ms 61760 KB Output is correct
14 Correct 90 ms 62804 KB Output is correct
15 Correct 86 ms 63024 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 58092 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 58200 KB Output is correct
25 Correct 8 ms 58308 KB Output is correct