Submission #118562

#	Time	Username	Problem	Language	Result	Execution time	Memory
118562		DystoriaX	Paths (BOI18_paths)	C++14	100 / 100	839 ms	97528 KiB

paths

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
int col[300010];
vector<int> adj[300010];
long long dp[300010][1 << 5], ans;

int main() {
	scanf("%d%d%d", &n, &m, &k);
	
	for(int i = 1; i <= n; i++) scanf("%d", &col[i]), col[i]--;
	
	while(m--){
		int u, v;
		
		scanf("%d%d", &u, &v);
		
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	
	for(int i = 1; i <= n; i++) dp[i][1 << col[i]] = 1;
	
	for(int len = 2; len <= k; len++){
		for(int i = 1; i <= n; i++){
			for(int mask = 0; mask < (1 << k); mask++){
				if(__builtin_popcount(mask) != len - 1) continue;
				
				for(auto v : adj[i]){
					if(!(mask & (1 << col[v]))){
						dp[v][mask | (1 << col[v])] += dp[i][mask];
					}
				}
			}
		}
	}
	
	for(int i = 1; i <= n; i++)
	    for(int mask = 0; mask < (1 << k); mask++)
	        if(__builtin_popcount(mask) > 1) ans += dp[i][mask];
	
	printf("%lld\n", ans);
	
	return 0;
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:10:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
paths.cpp:12:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; i++) scanf("%d", &col[i]), col[i]--;
                              ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
paths.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30