Submission #564642

#	Time	Username	Problem	Language	Result	Execution time	Memory
564642		Abrar_Al_Samit	Paths (BOI18_paths)	C++17	100 / 100	354 ms	97164 KiB

paths

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

const int MX = 3e5 + 5;
vector<int>g[MX];
int n, m, k;
int tag[MX];

long long ans = 0;
long long dp[MX][32];

int bit(int x) {
  return __builtin_popcount(x);
}
long long solve(int v, int mask) {
  long long &ret = dp[v][mask];
  if(ret!=-1) return ret;
  ret = 0;
  if(bit(mask)>1) {
    ret = 1;
  }
  for(int u : g[v]) if(~mask>>tag[u]&1) {
    ret += solve(u, mask|(1<<tag[u]));
  }
  return ret;
}
void PlayGround() {
  cin>>n>>m>>k;
  for(int i=1; i<=n; ++i) {
    cin>>tag[i];
    --tag[i];
  }
  for(int i=0; i<m; ++i) {
    int u, v;
    cin>>u>>v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  if(k==1) {
    cout<<0<<'\n';
    return;
  }


  memset(dp, -1, sizeof dp);
  for(int i=1; i<=n; ++i) {
    ans += solve(i, (1<<tag[i]));
  }
  cout<<ans<<'\n';

}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  PlayGround();
  return 0;
}

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