제출 #118562

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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;
}

컴파일 시 표준 에러 (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);
   ~~~~~^~~~~~~~~~~~~~~~

• 서브태스크 1: 23 / 23
• 서브태스크 2: 20 / 20
• 서브태스크 3: 27 / 27
• 서브태스크 4: 30 / 30