Submission #1061400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061400		warrenn	Paths (BOI18_paths)	C++14	100 / 100	332 ms	62556 KiB

paths

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

signed main(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<int>adj[n+1];
    int a[n+1];
    for(int q=0;q<n;q++){
        cin>>a[q];
        a[q]--;
    }
    for(int q=1;q<=m;q++){
        int u,v;
        cin>>u>>v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int ans=0;
    int dp[n+1][(1<<k)];
    memset(dp,0,sizeof dp);

    for(int q=0;q<n;q++){
        dp[q][(1<<a[q])]=1;
    }
   
    for(int apa=1;apa<(1<<k);apa++){
        for(int q=0;q<n;q++){
            if(!(apa & (1<<a[q])))continue;
            for(auto v : adj[q]){
                dp[q][apa]+=dp[v][(apa-(1<<a[q]))];
               // cout<<dp[q][apa]<<endl;
            }
        }
    }
    for(int q=0;q<n;q++){
        for(int w=1;w<(1<<k);w++){
            ans+=dp[q][w];
        }
    }
    cout<<ans-n<<endl;
}

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