Submission #1188652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188652		peteza	Paths (BOI18_paths)	C++20	100 / 100	261 ms	92756 KiB

paths

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

int n, m, k, a, b;
ll dp[300005][1<<5];
vector<int> adj[300005];
int col[300005];

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++) {
        cin >> col[i];
        col[i]--;
        dp[i][1<<col[i]] = 1;
    }
    while(m--) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    ll sum = 0;
    for(int cst = 0; cst < (1 << k); cst++) {
        for(int i=1;i<=n;i++) {
            for(auto &e:adj[i]) {
                if((cst >> col[e]) & 1) continue;
                dp[e][cst | (1 << col[e])] += dp[i][cst];
            }
            sum += dp[i][cst];
            //cout << dp[i][cst] << ' ';
        }
        //cout << '\n';
    }
    cout << sum-n;

}

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