Submission #1216433

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216433		HasanV11010238	Paths (BOI18_paths)	C++20	100 / 100	364 ms	66324 KiB

paths

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define mod 998244353
#define MAX 2000
int main(){
    ll n, m, k, a, b;
    cin>>n>>m>>k;
    vector<vector<int>> v(n + 1);
    vector<int> col(n + 1, 0);
    for (int i = 1; i <= n; i++){
        cin>>col[i];
        col[i]--;
    }
    for (int i = 0; i < m; i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int ti = (1<<k);
    vector<vector<ll>> dp(n + 1, vector<ll>(ti, 0));
    for (int i = 1; i <= n; i++){
        dp[i][(1<<col[i])]++;
    }
    for (int i = 0; i < ti; i++){
        for (int j = 1; j <= n; j++){
            for (auto el : v[j]){
                int val = i & (1<<col[el]);
                if (val != 0) continue;
                int to = i | (1<<col[el]);
                dp[el][to] += dp[j][i];
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < ti; j++) ans += dp[i][j];
    }
    cout<<ans - n<<"\n";
}

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