Submission #556470

#	Time	Username	Problem	Language	Result	Execution time	Memory
556470		eecs	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	25 ms	332 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 65 / 65