oj.uz

Submission #716437

# Submission time Handle Problem Language Result Execution time Memory
716437 2023-03-30T05:59:02 Z Iliya Paths (BOI18_paths) C++17
23 / 100
 530 ms 118880 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];
int 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("%I64d", &C[i]), C[i]--, dp[i][1 << C[i]] = 1;
	for (int i = 0, u, v; i < m; i++) 
		scanf("%I64d%I64d", &u, &v), Adj[u].pb(v), Adj[v].pb(u);
	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])];
			ans += dp[i][mask];
		}
	}
	printf("%I64d\n", 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:14: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   14 |   scanf("%I64d", &C[i]), C[i]--, dp[i][1 << C[i]] = 1;
      |          ~~~~^   ~~~~~
      |              |   |
      |              |   long long int*
      |              int*
      |          %I64lld
paths.cpp:16:14: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   16 |   scanf("%I64d%I64d", &u, &v), Adj[u].pb(v), Adj[v].pb(u);
      |          ~~~~^        ~~
      |              |        |
      |              int*     long long int*
      |          %I64lld
paths.cpp:16:19: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   16 |   scanf("%I64d%I64d", &u, &v), Adj[u].pb(v), Adj[v].pb(u);
      |               ~~~~^       ~~
      |                   |       |
      |                   int*    long long int*
      |               %I64lld
paths.cpp:23:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   23 |  printf("%I64d\n", ans);
      |          ~~~~^     ~~~
      |              |     |
      |              int   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("%I64d", &C[i]), C[i]--, dp[i][1 << C[i]] = 1;
      |   ~~~~~^~~~~~~~~~~~~~~~
paths.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%I64d%I64d", &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 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 7360 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 248 ms 16124 KB Output is correct
2 Correct 207 ms 14632 KB Output is correct
3 Correct 530 ms 118880 KB Output is correct
4 Correct 374 ms 25548 KB Output is correct
5 Correct 303 ms 25552 KB Output is correct
6 Incorrect 428 ms 83524 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 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 7360 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 248 ms 16124 KB Output is correct
12 Correct 207 ms 14632 KB Output is correct
13 Correct 530 ms 118880 KB Output is correct
14 Correct 374 ms 25548 KB Output is correct
15 Correct 303 ms 25552 KB Output is correct
16 Incorrect 428 ms 83524 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 78 ms 9680 KB Output isn't correct
3 Halted 0 ms 0 KB -