제출 #1268684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268684		pinbu	Paths (BOI18_paths)	C++20	100 / 100	284 ms	92836 KiB

paths

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

const int N = 300005, MOD = 1e9 + 7;
const int64_t oo = 1e18;

int n, m, k, c[N]; vector<int> adj[N];
int64_t dp[N][1 << 5];

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> c[i], c[i]--, dp[i][1 << c[i]] = 1;
    while (m--) {
    	int u, v; cin >> u >> v;
    	adj[u].emplace_back(v);
    	adj[v].emplace_back(u);
    }
    for (int ma = 0; ma < (1 << k); ma++) {
    	for (int u = 1; u <= n; u++) {
    		for (int v: adj[u]) {
    			if ((ma >> c[v]) & 1) {
    				dp[v][ma] += dp[u][ma ^ (1 << c[v])];
    			}
    		}
    	}
    }
    int64_t ans = 0;
    for (int u = 1; u <= n; u++) {
    	for (int ma = 0; ma < (1 << k); ma++) {
    		if (__builtin_popcount(ma) < 2) continue;
    		// if (((ma >> c[u]) & 1) == 0) assert(!dp[u][ma]);
    		ans += dp[u][ma];
    		// cerr << dp[u][ma] << ' ';
    	}
    	// cerr << '\n';
    }
    cout << ans;
    
    return 0;
}

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