oj.uz

Submission #975647

# Submission time Handle Problem Language Result Execution time Memory
975647 2024-05-05T15:58:14 Z Isam Paths (BOI18_paths) C++17
23 / 100
 62 ms 37692 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define eb emplace_back
 
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: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 5 ms 31324 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 5 ms 31324 KB Output is correct
5 Correct 5 ms 31324 KB Output is correct
6 Correct 5 ms 31424 KB Output is correct
7 Correct 5 ms 31324 KB Output is correct
8 Correct 5 ms 31196 KB Output is correct
9 Correct 5 ms 31324 KB Output is correct
10 Correct 6 ms 31324 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 37692 KB Output is correct
2 Correct 55 ms 37256 KB Output is correct
3 Incorrect 12 ms 32348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31324 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 5 ms 31324 KB Output is correct
5 Correct 5 ms 31324 KB Output is correct
6 Correct 5 ms 31424 KB Output is correct
7 Correct 5 ms 31324 KB Output is correct
8 Correct 5 ms 31196 KB Output is correct
9 Correct 5 ms 31324 KB Output is correct
10 Correct 6 ms 31324 KB Output is correct
11 Correct 62 ms 37692 KB Output is correct
12 Correct 55 ms 37256 KB Output is correct
13 Incorrect 12 ms 32348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31320 KB Output is correct
2 Incorrect 44 ms 33264 KB Output isn't correct
3 Halted 0 ms 0 KB -