Submission #541235

#	Time	Username	Problem	Language	Result	Execution time	Memory
541235		AlperenT	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	18 ms	340 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int N = 60 + 5, MOD = 1e9 + 7;

struct mint{
    int val = 0;
 
    mint(long long a = 0) : val(a % MOD) {if(val < 0) val += MOD; }
    mint(long long a, long long b) {*this += a; *this /= b; }
 
    mint &operator += (const mint &b) {val += b.val; if(val >= MOD) val -= MOD; return *this; }
    mint &operator -= (const mint &b) {val -= b.val; if(val < 0) val += MOD; return *this; }
    mint &operator *= (const mint &b) {val = (1ll * val * b.val) % MOD; return *this; }
 
    mint mexp(mint a, long long b){
        mint c(1);
        for(; b > 0; b /= 2, a *= a) if(b & 1) c *= a;
        return c;
    }
 
    mint minv(const mint &a) {return mexp(a, MOD - 2); };
 
    mint &operator /= (const mint &b) {*this *= minv(b); 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 - (const mint &a) {return 0 - a; }
    friend mint operator * (mint a, const mint &b) {return a *= b; }
    friend mint operator / (mint a, const mint &b) {return a /= b; }
 
    friend bool operator == (const mint &a, const mint &b) {return a.val == b.val; }
    friend bool operator != (const mint &a, const mint &b) {return a.val != b.val; }
 
    friend istream &operator >> (istream &is, mint &a) {long long b; is >> b; a = b; return is; }
    friend ostream &operator << (ostream &os, const mint &a) {return os << a.val; }
};

int n, m, k, a, b;

mint ans;

struct DSU{
    int par[N], stsize[N], setcnt;

    void reset(int n){
        for(int i = 1; i <= n; i++) par[i] = i, stsize[i] = 1;
        setcnt = n;
    }

    int setfind(int a){
        if(a == par[a]) return a;
        else return par[a] = setfind(par[a]);
    }

    void setunion(int a, int b){
        a = setfind(a), b = setfind(b);

        if(a != b){
            if(stsize[b] > stsize[a]) swap(a, b);

            par[b] = par[a];
            stsize[a] += stsize[b];

            setcnt--;
        }
    }
};

DSU dsu;

vector<pair<int, int>> tree[N];

vector<int> paths[N];

pair<int, int> pairs[N], par[N];

void dfs(int v, int p){
    for(auto e : tree[v]){
        if(e.first != p){
            par[e.first] = {v, e.second};
            dfs(e.first, v);
        }
    }
}

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

    cin >> n >> m >> k;

    for(int i = 1; i <= n - 1; i++){
        cin >> a >> b;

        tree[a].push_back({b, i});
        tree[b].push_back({a, i});
    }

    for(int i = 1; i <= m; i++) cin >> pairs[i].first >> pairs[i].second;

    for(int i = 1; i <= m; i++){
        par[pairs[i].first] = {0, 0};

        dfs(pairs[i].first, 0);

        int v = pairs[i].second;

        while(par[v].first != 0){
            paths[i].push_back(par[v].second);

            v = par[v].first;
        }
    }

    for(int msk = 0; msk < (1 << m); msk++){
        dsu.reset(n - 1);

        for(int i = 0; i < m; i++){
            if(msk & (1 << i)){
                for(int j = 0; j < (int)paths[i + 1].size() - 1; j++) dsu.setunion(paths[i + 1][j], paths[i + 1][j + 1]);
            }
        }

        ans += mint().mexp(k, dsu.setcnt) * (__builtin_popcount(msk) % 2 == 0 ? 1 : -1);
    }

    cout << ans;
}

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