Submission #702061

#	Time	Username	Problem	Language	Result	Execution time	Memory
702061		_martynas	Paths (BOI18_paths)	C++11	100 / 100	544 ms	56676 KiB

paths

// Solved on 2022/10/18
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const int MOD = 1e9+7;

#define F first
#define S second
#define PB push_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

void FASTIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); }

const int MXN = 3e5+5;

int n, m, k;
int A[MXN];
vi adj[MXN];
ll ways[1<<6][MXN];

void transit(int bits) {
    for(int i = 0; i < n; i++) {
        for(int j : adj[i]) {
            for(int b = 0; b < (1<<k); b++) {
                if(__builtin_popcount(b) != bits) continue;
                if(b & (1 << A[j])) continue;
                ways[b | (1 << A[j])][j] += ways[b][i];
            }
        }
    }
}

int main() {
    FASTIO();

    cin >> n >> m >> k;
    for(int i = 0; i < n; i++) {
        cin >> A[i]; A[i]--;
        ways[1<<A[i]][i]++;
    }

    for(int i = 0; i < m; i++) {
        int a, b; cin >> a >> b; a--, b--;
        adj[a].PB(b);
        adj[b].PB(a);
    }

    for(int b = 1; b < k; b++) transit(b);

    ll ans = 0;
    for(int b = 0; b < (1<<k); b++) {
        for(int i = 0; i < n; i++) {
            ans += ways[b][i];
        }
    }
    cout << ans-n << "\n";

    return 0;
}

/*



*/

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