제출 #1126371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1126371		AverageAmogusEnjoyer	Paths (BOI18_paths)	C++20	100 / 100	1106 ms	66352 KiB

paths

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);

int rng() { 
    return ui(mrand);
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    int n,m,k;
    cin >> n >> m >> k;
    vector<int> a(n);
    for (int &x: a) {
        cin >> x;
        --x;
    }
    vector<vector<int>> adj(n);
    for (int u,v;m--;) {
        cin >> u >> v;
        --u,--v;
        adj[u].push_back(v),adj[v].push_back(u);
    }
    vector<vector<ll>> dp(n,vector<ll>(1 << k));
    for (int i=0;i<n;i++) 
        dp[i][1 << a[i]] = 1;
    for (int mask = 0; mask < (1 << k); mask++) {
        for (int u = 0; u < n; u++) {
            for (int &v: adj[u]) {
                if ((mask >> a[v]) & 1) continue;
                dp[v][mask | (1 << a[v])] += dp[u][mask];
            }
        }
    }
    ll ans = 0;
    for (int i=0;i<n;i++)
        for (int j=0;j<(1<<k);j++)
            ans += dp[i][j];
    cout << ans - n << endl;
}

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