Submission #1268685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268685		pinbu	Paths (BOI18_paths)	C++20	100 / 100	222 ms	92736 KiB

paths

#include <iostream>
#include <vector>
using namespace std;

const int N = 300005;

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 = 1; ma < (1 << k); ma++) {
    	for (int u = 1; u <= n; u++) {
    		if ((ma >> c[u]) & 1) {
    			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 = 3; ma < (1 << k); ma++) {
    		if (__builtin_popcount(ma) < 2) continue;
    		ans += dp[u][ma];
    	}
    }
    cout << ans;
    
    return 0;
}

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