Submission #866411

#	Time	Username	Problem	Language	Result	Execution time	Memory
866411		The_Samurai	Paths (BOI18_paths)	C++17	100 / 100	347 ms	61264 KiB

paths

//#pragma GCC optimize("O3", "unroll-loops")
//#pragma GCC target("avx2", "popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e18;

vector<int> col_v;
vector<vector<int>> g;
ll ans;

int main() {
    srand(time(0));
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int n, m, k;
    cin >> n >> m >> k;
    col_v.assign(n + 1, 0);
    g.assign(n + 1, {});
    for (int i = 1; i <= n; i++) cin >> col_v[i];
    for (int i = 1; i <= n; i++) col_v[i] = 1 << (col_v[i] - 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector dp(1 << k, vector(n + 1, 0ll));
    for (int i = 1; i <= n; i++) dp[col_v[i]][i] = 1;
    for (int bt = 1; bt < (1 << k); bt++) {
        for (int u = 1; u <= n; u++) {
            for (int v: g[u]) {
                if (bt & col_v[v]) continue;
                dp[bt | col_v[v]][v] += dp[bt][u];
            }
        }
        if (__builtin_popcount(bt) == 1) continue;
        for (int u = 1; u <= n; u++) ans += dp[bt][u];
    }
    cout << ans;
}

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