Submission #392898

#	Time	Username	Problem	Language	Result	Execution time	Memory
392898		arujbansal	Paths (BOI18_paths)	C++17	23 / 100	309 ms	30832 KiB

paths

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long

const int MXN = 1e5 + 5, INF = 1e9 + 5;

void solve() {
    int N, M, K;
    cin >> N >> M >> K;

    vector<vector<int>> dp(1 << K, vector<int>(N, 0));
    vector<int> colour(N);

    for (int i = 0; i < N; i++) {
        cin >> colour[i];
        colour[i]--;

        dp[1 << colour[i]][i] = 1;
    }

    vector<int> g[N];
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    int ans = 0;

    for (int mask = 0; mask < (1 << K); mask++) {
        for (int u = 0; u < N; u++) {
            if ((mask >> colour[u]) & 1) {
                for (const auto &v : g[u])
                    dp[mask][u] += dp[mask ^ (1 << colour[u])][v];

                ans += dp[mask][u]; 
            }
        }
    }

    cout << ans - N;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}

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