Submission #868638

#	Time	Username	Problem	Language	Result	Execution time	Memory
868638		mzh	Šarenlist (COCI22_sarenlist)	C++17	0 / 110	1 ms	348 KiB

Main

#include <bits/stdc++.h>

using namespace std;

/*
    this problem can be solved using inclusion exclusion
    but the implementation is a little tricky
    it's annoying that we need to color edges in this problem
    how do we handle this?

    number the edges, make an adjacency list containing (dest, edge index)
    for each path, get its set of edges using dfs
    when processing a subset, make a dsu on sets of edges
    add/subtract k^sets
*/

constexpr int MOD = 1e9 + 7;

constexpr int N = 60, M = 15;

pair<int, int> edges[N];
vector<pair<int, int>> adj[N];
pair<int, int> paths[M];

pair<int, int> from[N];

void dfs(int u, int p) {
    for (auto [v, idx] : adj[u]) {
        if (v != p) {
            from[v] = {u, idx};
            dfs(v, u);
        }
    }
}

int dsu[N];
int comps = 0;

int find(int x) {
    return dsu[x] < 0 ? x : dsu[x] = find(dsu[x]);
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);

    if (x == y) {
        return;
    }
    if (-dsu[x] < -dsu[y]) {
        swap(x, y);
    }

    dsu[x] += dsu[y];
    dsu[y] = x;
    comps--;
}

int bin_exp(int base, int exp) {
    int ret = 1;
    while (exp != 0) {
        if (exp & 1) {
            ret = 1ll * ret * base % MOD;
        }
        base = 1ll * base * base % MOD;
        exp >>= 1;
    }
    return ret;
}

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

    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 0; i < n - 1; i++) {
        auto &[u, v] = edges[i];
        cin >> u >> v;
        u--; v--;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    for (int i = 0; i < m; i++) {
        auto &[a, b] = paths[i];
        cin >> a >> b;
        a--; b--;
    }

    long long ans = 0;
    for (int i = 0; i < (1 << m); i++) {
        fill(dsu, dsu + n - 1, -1);
        comps = n - 1;

        for (int j = 0; j < m; j++) {
            if ((i >> j) & 1) {
                auto [a, b] = paths[j];
                from[a].first = a;
                dfs(a, -1);
                for (int x = b; x != a; x = from[x].first) {
                    unite(from[x].second, from[from[x].first].second);
                }
            }
        }

        if (__builtin_popcount(i) & 1) {
            ans = (ans - bin_exp(k, comps) + MOD) % MOD;
        } else {
            ans = (ans + bin_exp(k, comps)) % MOD;
        }
    }
    cout << ans << '\n';
    
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 65