Submission #387545

#	Time	Username	Problem	Language	Result	Execution time	Memory
387545		kimbj0709	Paths (BOI18_paths)	C++14	100 / 100	1291 ms	99880 KiB

paths

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 300050
vector<vector<int> > adj(maxn);
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int n,m,k;
  int input1,input2;
  cin >> n >> m >> k;
  vector<int> color(maxn);
  for(int i=0;i<n;i++){
    cin >> color[i];
    color[i]--;
  }
  for(int i=0;i<m;i++){
    cin >> input1 >> input2;
    input1--,input2--;
    adj[input1].push_back(input2);
    adj[input2].push_back(input1);
  }
  int ans = 0;
  int dp[n][(1<<k)];
  memset(dp,0,sizeof(dp));
  for(int i=0;i<n;i++){
    dp[i][(1<<color[i])] = 1;
  }
  int next[n][(1<<k)];
  for(int aa=0;aa<k;aa++){
    memset(next,0,sizeof(next));
    for(int i=0;i<n;i++){
      for(auto j:adj[i]){
        for(int l=0;l<(1<<k);l++){
          if(((1<<color[j])&l)==0){
            int nextnum = (1<<color[j])|l;
            next[j][nextnum] += dp[i][l];
          }
        }
      }
    }
    for(int i=0;i<n;i++){
      for(int j=0;j<(1<<k);j++){
        ans += next[i][j];
        dp[i][j] = next[i][j];
        next[i][j] = 0;
      }
    }
  }
  cout << ans;
}

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