Submission #716432

#	Time	Username	Problem	Language	Result	Execution time	Memory
716432		Iliya	Paths (BOI18_paths)	C++17	23 / 100	309 ms	118820 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];
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 (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: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 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30