oj.uz

Submission #868638

# Submission time Handle Problem Language Result Execution time Memory
868638 2023-11-01T04:19:00 Z mzh Šarenlist (COCI22_sarenlist) C++17
0 / 110
 1 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -