oj.uz

Submission #541235

# Submission time Handle Problem Language Result Execution time Memory
541235 2022-03-22T19:59:07 Z AlperenT Šarenlist (COCI22_sarenlist) C++17
110 / 110
 18 ms 340 KB 
#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.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 320 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 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 0 ms 320 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 320 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 324 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 324 KB Output is correct
7 Correct 1 ms 212 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 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 2 ms 324 KB Output is correct
6 Correct 2 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 1 ms 212 KB Output is correct
3 Correct 1 ms 320 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 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 320 KB Output is correct
11 Correct 1 ms 324 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 324 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 316 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 324 KB Output is correct
24 Correct 2 ms 324 KB Output is correct
25 Correct 2 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 7 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 8 ms 212 KB Output is correct
31 Correct 3 ms 324 KB Output is correct
32 Correct 2 ms 212 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 4 ms 212 KB Output is correct
36 Correct 18 ms 212 KB Output is correct
37 Correct 8 ms 324 KB Output is correct