Submission #1125122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125122		Zero_OP	Šarenlist (COCI22_sarenlist)	C++20	110 / 110	13 ms	328 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
const int MAX = 100;

struct mint{
    int v;
    mint() : v(0) {}
    mint(int v) : v(v) {}
    mint& operator += (const mint& o){ v += o.v; if(v >= mod) v -= mod; return *this; }
    mint& operator -= (const mint& o){ v -= o.v; if(v < 0) v += mod; return *this; }
    mint& operator *= (const mint& o){ v = 1ll * v * o.v % mod; return *this; }

    friend mint operator + (mint a, const mint& b){ return a += b; }
    friend mint operator - (mint a, const mint& b){ return a -= b; }
    friend mint operator * (mint a, const mint& b){ return a *= b; }
};

int N, M, K, depth[MAX], par[MAX];
vector<int> adj[MAX], paths[MAX];
mint pw_k[MAX];

void dfs(int u, int p){
    for(auto v : adj[u]) if(v != p){
        par[v] = u;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}

vector<int> get_path(int u, int v){ //exclude lca(u, v)
    vector<int> vt;
    while(depth[u] > depth[v]) vt.push_back(u), u = par[u];
    while(depth[u] < depth[v]) vt.push_back(v), v = par[v];
    while(u != v){
        vt.push_back(u);
        vt.push_back(v);
        u = par[u]; v = par[v];
    }
    return vt;
}

int lab[MAX];

int root(int u){
    return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
}

bool join(int u, int v){
    u = root(u);
    v = root(v);
    if(u == v) return false;
    if(lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
    return true;
}

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

    cin >> N >> M >> K;
    for(int i = 0; i + 1 < N; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    dfs(0, -1);

    for(int i = 0; i < M; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        paths[i] = get_path(u, v);
    }

    pw_k[0] = 1;
    for(int i = 1; i <= N; ++i) pw_k[i] = pw_k[i - 1] * mint(K);

    mint all_combinations = pw_k[N - 1];
    mint inv = 0;
    for(int mask = 1; mask < (1 << M); ++mask){
        fill(lab + 1, lab + N, -1);

        for(int i = 0; i < M; ++i){
            if(mask >> i & 1){
                int base = paths[i][0];
                for(auto u : paths[i]){
                    join(base, u);
                }
            }
        }

        int cnt_same = 0;
        for(int i = 1; i < N; ++i){
            if(root(i) == i) ++cnt_same;
        }

        if(__builtin_popcount(mask) & 1) inv += pw_k[cnt_same];
        else inv -= pw_k[cnt_same];
    }

    mint ans = all_combinations - inv;
    cout << ans.v << '\n';

    return 0;
}

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