Submission #716416

#	Time	Username	Problem	Language	Result	Execution time	Memory
716416		Iliya	Paths (BOI18_paths)	C++17	23 / 100	308 ms	66332 KiB

paths

#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 << k); 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 << k); mask++) 
			if (ones(mask) != 1) ans += dp[i][mask];
	printf("%I64d", ans);
	return 0;
}

Compilation message (stderr)

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