oj.uz

Submission #716417

# Submission time Handle Problem Language Result Execution time Memory
716417 2023-03-30T05:04:08 Z Iliya Paths (BOI18_paths) C++17
23 / 100
 305 ms 115404 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ones(x) __builtin_popcount(x)
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
int n, m, k, C[N];
ll ans, dp[N][(1 << 5) + 10];
vector<int> Adj[N];
signed main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d", &C[i]), C[i]--;
	for (int i = 0, u, v; i < m; i++)
		scanf("%d%d", &u, &v), Adj[u].pb(v), Adj[v].pb(u);
	for (int i = 1; i <= n; i++) 
		dp[i][(1 << C[i])] = 1;
	for (int mask = 1; mask < (1 << k); mask++) if (ones(mask) != 1) 
		for (int i = 1; i <= n; i++) if (mask & (1 << C[i]))
			for (int u : Adj[i]) if ((mask & (1 << C[u])) and C[u] != C[i])
				dp[i][mask] += dp[u][mask ^ (1 << C[i])];
	for (int i = 1; i <= n; i++)
		for (int mask = 1; mask < (1 << k); mask++) 
			if (ones(mask) != 1) ans += dp[i][mask];
	printf("%I64d", ans);
	return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:25:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long int'} [-Wformat=]
   25 |  printf("%I64d", ans);
      |          ~~~~^   ~~~
      |              |   |
      |              int ll {aka long long int}
      |          %I64lld
paths.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
paths.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d", &C[i]), C[i]--;
      |   ~~~~~^~~~~~~~~~~~~
paths.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d%d", &u, &v), Adj[u].pb(v), Adj[v].pb(u);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7252 KB Output is correct
2 Correct 6 ms 7292 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7360 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7300 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 4 ms 7252 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 12616 KB Output is correct
2 Correct 79 ms 11116 KB Output is correct
3 Correct 305 ms 115404 KB Output is correct
4 Correct 101 ms 21640 KB Output is correct
5 Correct 105 ms 21836 KB Output is correct
6 Incorrect 218 ms 80988 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7252 KB Output is correct
2 Correct 6 ms 7292 KB Output is correct
3 Correct 5 ms 7380 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7360 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7300 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 4 ms 7252 KB Output is correct
11 Correct 89 ms 12616 KB Output is correct
12 Correct 79 ms 11116 KB Output is correct
13 Correct 305 ms 115404 KB Output is correct
14 Correct 101 ms 21640 KB Output is correct
15 Correct 105 ms 21836 KB Output is correct
16 Incorrect 218 ms 80988 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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