oj.uz

Submission #716432

# Submission time Handle Problem Language Result Execution time Memory
716432 2023-03-30T05:48:35 Z Iliya Paths (BOI18_paths) C++17
23 / 100
 309 ms 118820 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ones(x) __builtin_popcountll(x)
#define int long long
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("%I64d%I64d%I64d", &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]) 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 and (mask & (1 << C[i]))) ans += dp[i][mask];
	printf("%I64d", ans);
	return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:12:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   12 |  scanf("%I64d%I64d%I64d", &n, &m, &k);
      |         ~~~~^             ~~
      |             |             |
      |             int*          long long int*
      |         %I64lld
paths.cpp:12:18: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   12 |  scanf("%I64d%I64d%I64d", &n, &m, &k);
      |              ~~~~^            ~~
      |                  |            |
      |                  int*         long long int*
      |              %I64lld
paths.cpp:12:23: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
   12 |  scanf("%I64d%I64d%I64d", &n, &m, &k);
      |                   ~~~~^           ~~
      |                       |           |
      |                       int*        long long int*
      |                   %I64lld
paths.cpp:14:11: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   14 |   scanf("%d", &C[i]), C[i]--;
      |          ~^   ~~~~~
      |           |   |
      |           |   long long int*
      |           int*
      |          %lld
paths.cpp:16:11: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   16 |   scanf("%d%d", &u, &v), Adj[u].pb(v), Adj[v].pb(u);
      |          ~^     ~~
      |           |     |
      |           int*  long long int*
      |          %lld
paths.cpp:16:13: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   16 |   scanf("%d%d", &u, &v), Adj[u].pb(v), Adj[v].pb(u);
      |            ~^       ~~
      |             |       |
      |             int*    long long int*
      |            %lld
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:12:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  scanf("%I64d%I64d%I64d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%d", &C[i]), C[i]--;
      |   ~~~~~^~~~~~~~~~~~~
paths.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   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 5 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7396 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 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 81 ms 16180 KB Output is correct
2 Correct 64 ms 14660 KB Output is correct
3 Correct 309 ms 118820 KB Output is correct
4 Correct 143 ms 25520 KB Output is correct
5 Correct 109 ms 25460 KB Output is correct
6 Incorrect 214 ms 83532 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 5 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7396 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 4 ms 7252 KB Output is correct
11 Correct 81 ms 16180 KB Output is correct
12 Correct 64 ms 14660 KB Output is correct
13 Correct 309 ms 118820 KB Output is correct
14 Correct 143 ms 25520 KB Output is correct
15 Correct 109 ms 25460 KB Output is correct
16 Incorrect 214 ms 83532 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

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