oj.uz

Submission #556470

# Submission time Handle Problem Language Result Execution time Memory
556470 2022-05-03T08:25:34 Z eecs Šarenlist (COCI22_sarenlist) C++17
110 / 110
 25 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 65, P = 1000000007;
int n, m, K, u[maxn], v[maxn], fa[maxn], dep[maxn], bel[maxn];
vector<int> G[maxn];

int qp(int x, int y) {
    int z = 1;
    for (; y; y >>= 1, x = 1LL * x * x % P) {
        if (y & 1) z = 1LL * z * x % P;
    }
    return z;
}

int find(int x) {
    return x == bel[x] ? x : bel[x] = find(bel[x]);
}

int main() {
    scanf("%d %d %d", &n, &m, &K);
    for (int i = 1, u, v; i < n; i++) {
        scanf("%d %d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u[i], &v[i]);
    }
    auto dfs = [&](auto self, int u) -> void {
        dep[u] = dep[fa[u]] + 1;
        for (int v : G[u]) if (v ^ fa[u]) {
            fa[v] = u, self(self, v);
        }
    };
    dfs(dfs, 1);
    int ans = 0;
    for (int S = 0; S < 1 << m; S++) {
        iota(bel + 2, bel + n + 1, 2);
        for (int i = 0; i < m; i++) if (S >> i & 1) {
            int x = u[i], y = v[i], o = 0;
            while (x ^ y) {
                if (dep[x] < dep[y]) swap(x, y);
                if (o) bel[find(o)] = find(x);
                o = x, x = fa[x];
            }
        }
        int cnt = 0;
        for (int i = 2; i <= n; i++) {
            if (i == find(i)) cnt++;
        }
        ans = (ans + 1LL * qp(K, cnt) * (__builtin_parity(S) ? P - 1 : 1)) % P;
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d %d %d", &n, &m, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d %d", &u[i], &v[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
65.0 / 65.0

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