Submission #162983

#	Time	Username	Problem	Language	Result	Execution time	Memory
162983		Minnakhmetov	Paths (BOI18_paths)	C++14	100 / 100	793 ms	322072 KiB

paths

#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

const int N = 3e5 + 5, K = 5;
int a[N];
vector<int> g[N];
ll dp[K][N][1 << K];
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 0; i < n; i++) {
    	cin >> a[i];
    	a[i]--;
    	dp[0][i][1 << a[i]] = 1;
    }

    for (int i = 0; i < m; i++) {
    	int x, y;
    	cin >> x >> y;
    	x--, y--;
    	g[x].push_back(y);
    	g[y].push_back(x);
    }

    for (int i = 1; i < k; i++) {
    	for (int j = 0; j < n; j++) {
    		for (int to : g[j]) {
    			int h = (1 << k) - 1 - (1 << a[j]);
    			for (int z = h; z != 0; z = (z - 1) & h) {
    				dp[i][j][z | (1 << a[j])] += dp[i - 1][to][z];
    			}
    		}
    	}
    }

    ll ans = 0;
    for (int i = 1; i < k; i++) {
    	for (int j = 0; j < n; j++) {
    		for (int z = 0; z < (1 << k); z++) {
    			ans += dp[i][j][z];
    		}
    	}
    }

    cout << ans;

    return 0;
}

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