Submission #1272434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272434		phamminhson	Paths (BOI18_paths)	C++20	100 / 100	375 ms	92624 KiB

paths

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

int n, m, k;
long long int res = 0;

long long int dp[300005][32];
vector<int> Adj[300005];

int arr[300005];

int main(){
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; i ++){
        cin >> arr[i];
        dp[i][0] = 1;
    }

    for(int i = 1 ; i <= m ; i ++){
        int u, v;
        cin >> u >> v;
        Adj[u].push_back(v);
        Adj[v].push_back(u);
    }

    for(int mask = 1; mask < (1 << k); mask ++){
        for(int i = 1 ; i <= n ; i ++){
            if((mask >> (arr[i] - 1)) & 1){
                if(__builtin_popcount(mask) == 1){
                    dp[i][mask] = 1;
                    continue;
                }
                for(int j = 0; j < Adj[i].size(); j ++){
                    int v = Adj[i][j];
                    dp[i][mask] += dp[v][mask ^ (1 << (arr[i] - 1))];
                }
                if(__builtin_popcount(mask) > 1)
                        res += dp[i][mask];
                /*for(int j = k - 1 ; j >= 0 ; j --)
                    cout << ((mask >> j) & 1);
                cout << " " << i << " " << dp[i][mask] << endl;*/
            }
        }
    }

    cout << res << endl;
}

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