Submission #1107710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107710		ShadowShark	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	16 ms	592 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const long long mod = 1e9 + 7;
int n, m, k;
long long power[75];
bitset<75> edge[20];
vector<pair<int, int>> adj[75];
vector<int> graph[75];
int save[75], depth[75], par[75];
bool visited[75];

void pre_dfs(int u, int pre) {
    for (auto it: adj[u]) {
        int v = it.first, id = it.second;
        if (v == pre) continue;

        save[v] = id;
        depth[v] = depth[u] + 1;
        par[v] = u;

        pre_dfs(v, u);
    }
}

void dfs(int u, int mask) {
    visited[u] = true;
    for (auto v: graph[u]) {
        if (!visited[v] && (mask & (1 << (v - 1)))) dfs(v, mask);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> k;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    pre_dfs(1, 1);

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;

        if (depth[u] < depth[v]) swap(u, v);
        while (depth[u] != depth[v]) {
            edge[i][save[u]] = 1;
            u = par[u];
        }

        while (u != v) {
            edge[i][save[u]] = 1;
            edge[i][save[v]] = 1;
            u = par[u];
            v = par[v];
        }
    }

    for (int i = 1; i <= m; i++) {
        if (edge[i].count() < 2) {
            cout << 0;
            return 0;
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = i + 1; j <= m; j++) {
            bitset<75> calc = edge[i] & edge[j];
            if (calc.count()) {
                graph[i].push_back(j);
                graph[j].push_back(i);
                //cout << "graph " << i << ' ' << j << '\n';
            }
        }
    }

    power[0] = 1;
    for (int i = 1; i <= n; i++)
        power[i] = (1LL * k * power[i - 1]) % mod;

    long long ans = power[n - 1]; //cout << power[n - 1] << '\n';
    for (int mask = 1; mask < (1 << m); mask++) {
        bitset<75> keep; int com = 0, rem = n - 1;
        memset(visited, false, sizeof visited);
        for (int i = 1; i <= m; i++) {
            if (mask & (1 << (i - 1))) {
                keep = keep | edge[i];
                if (!visited[i]) {
                    com++;
                    dfs(i, mask);
                }
            }
        }
        rem = rem - keep.count();
        if (__builtin_popcount(mask) % 2 == 1) ans = (ans - power[rem + com] + mod) % mod;
            else ans = (ans + power[rem + com]) % mod;
        //cout << mask << ' ' << rem << ' ' << com << ' ' << ans << '\n';
    }

    cout << ans;

    return 0;
}

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