Submission #1191191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191191		meisgood	Paths (BOI18_paths)	C++20	53 / 100	255 ms	157688 KiB

paths

#include <bits/stdc++.h>
using namespace std ;
#define int long long
int arr[100003] ;
vector <int> adj[100003] ;
int dp[10][100003][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: 0 / 20
• Subtask 3: 0 / 27
• Subtask 4: 30 / 30