제출 #1172917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172917		nguyenkhangninh99	Paths (BOI18_paths)	C++17	100 / 100	241 ms	110100 KiB

paths

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

#define int long long

const int maxn = 4e5 + 5;
int color[maxn], dp[maxn][(1 << 5) + 5];

vector<int> g[maxn];
void solve(){
    int n, m, k; cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) cin >> color[i];
    for(int i = 1; i <= n; i++) dp[i][1 << (--color[i])] = 1;
    
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    int res = 0;
    for (int mask = 0; mask < (1 << k); mask++){
        for (int u = 1; u <= n; u++){
            if((mask >> color[u]) & 1){
                for (int v: g[u]){ 
                    if((mask >> color[v]) & 1) continue;
                    dp[v][mask ^ (1 << color[v])] += dp[u][mask];
                } 
                if(__builtin_popcount(mask) > 1) res += dp[u][mask];
            }
        }

    }
    cout << res;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    solve();
}

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