Submission #868711

#	Time	Username	Problem	Language	Result	Execution time	Memory
868711		mzh	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	41 ms	468 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 pow_k[N]; 

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--;
    }

    pow_k[0] = 1;
    for (int i = 1; i < n; i++) {
        pow_k[i] = 1ll * pow_k[i - 1] * k % MOD;
    }
 
    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; from[x].first != a; x = from[x].first) {
                    unite(from[x].second, from[from[x].first].second);
                }
            }
        }
 
        if (__builtin_popcount(i) & 1) {
            ans = (ans - pow_k[comps] + MOD) % MOD;
        } else {
            ans = (ans + pow_k[comps]) % MOD;
        }
    }
    cout << ans << '\n';
    
    return 0;
}

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