oj.uz

Submission #716415

# Submission time Handle Problem Language Result Execution time Memory
716415 2023-03-30T04:59:03 Z Iliya Paths (BOI18_paths) C++17
23 / 100
 513 ms 66160 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], dp[N][(1 << 5) + 10];
vector<int> Adj[N]; ll ans;
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 << 5); 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 << 5); mask++) 
			if (ones(mask) != 1) ans += dp[i][mask];
	printf("%I64d", ans);
	return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:24:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long int'} [-Wformat=]
   24 |  printf("%I64d", ans);
      |          ~~~~^   ~~~
      |              |   |
      |              int ll {aka long long int}
      |          %I64lld
paths.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
paths.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   scanf("%d", &C[i]), C[i]--;
      |   ~~~~~^~~~~~~~~~~~~
paths.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   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 4 ms 7252 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 3 ms 7252 KB Output is correct
10 Correct 4 ms 7292 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 11816 KB Output is correct
2 Correct 111 ms 11048 KB Output is correct
3 Correct 513 ms 66160 KB Output is correct
4 Correct 187 ms 16804 KB Output is correct
5 Correct 144 ms 16820 KB Output is correct
6 Incorrect 355 ms 48188 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 4 ms 7252 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 3 ms 7252 KB Output is correct
10 Correct 4 ms 7292 KB Output is correct
11 Correct 134 ms 11816 KB Output is correct
12 Correct 111 ms 11048 KB Output is correct
13 Correct 513 ms 66160 KB Output is correct
14 Correct 187 ms 16804 KB Output is correct
15 Correct 144 ms 16820 KB Output is correct
16 Incorrect 355 ms 48188 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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