제출 #1191192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191192		meisgood	Paths (BOI18_paths)	C++20	100 / 100	717 ms	471772 KiB

paths

#include <bits/stdc++.h>
using namespace std ;
#define int long long
int arr[300003] ;
vector <int> adj[300003] ;
int dp[10][300003][1<<5] ;
signed main(){
  int n,m,k,i,j ;
  cin >> n >> m >> k ;
  for (i = 1 ; i <= n ; i ++){
    cin >> arr[i] ;
    arr[i]-- ;
    dp[0][i][1<<arr[i]]=1 ;
  }
  for (i = 0 ; i < m ; i ++){
    int a,b ;
    cin >> a >> b ;
    adj[a].push_back(b) ;
    adj[b].push_back(a) ;
  }
  for (int ii = 1 ; ii <= 5 ; ii ++){
    for (i = 1 ; i <= n ; i ++){
      for (j = 0 ; j < (1<<k) ; j ++){
        if (j&(1<<arr[i])){
          for (auto a : adj[i]){
            dp[ii][i][j]+=dp[ii-1][a][j^(1<<arr[i])] ;
          }
        }
      }
    }
  }
  int tt=0 ;
  for (int ii = 1 ; ii <= 5 ; ii ++) for (i = 1 ; i <= n ; i ++) for (j = 0 ; j < (1<<k) ; j ++) tt+=dp[ii][i][j] ;
  cout << tt << endl ;
  return 0 ;
}

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