제출 #1133080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1133080		mnbvcxz123	Paths (BOI18_paths)	C++20	23 / 100	38 ms	6472 KiB

paths

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

constexpr int N=1e5+5;

int a[N];
vector<int>g[N];

int dp[1<<6][N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;++i){
      cin>>a[i];
      --a[i];dp[1<<a[i]][i]=1;
    }
    for(int i=0,a,b;i<m;++i){
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int msk=0;msk<(1<<k);++msk)
        for(int i=1;i<=n;++i){
            if(msk&(1<<a[i]))continue;
            for(const int&j:g[i]){
                if(!(msk&(1<<a[j])))continue;
                dp[msk^(1<<a[i])][i]+=dp[msk][j];
            }
        }
    int ans=0;
    for(int i=1;i<=n;++i)
        for(int msk=0;msk<(1<<k);++msk)
              ans+=dp[msk][i];
    cout<<ans-n<<'\n';
}

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