Submission #716437

#	Time	Username	Problem	Language	Result	Execution time	Memory
716437		Iliya	Paths (BOI18_paths)	C++17	23 / 100	530 ms	118880 KiB

paths

#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 (stderr)

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 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30