oj.uz

Submission #1107710

# Submission time Handle Problem Language Result Execution time Memory
1107710 2024-11-02T03:13:22 Z ShadowShark Šarenlist (COCI22_sarenlist) C++17
110 / 110
 16 ms 592 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 508 KB Output is correct
7 Correct 1 ms 336 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 3 ms 336 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct

Subtask #5
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 0 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 508 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 3 ms 336 KB Output is correct
25 Correct 3 ms 504 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 5 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 5 ms 336 KB Output is correct
31 Correct 2 ms 336 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 3 ms 336 KB Output is correct
36 Correct 16 ms 336 KB Output is correct
37 Correct 7 ms 336 KB Output is correct