Submission #1107734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107734		ToTenLinh	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	2 ms	4944 KiB

Main

#include <bits/stdc++.h>
#define fo(i,m,n) for(int i=m;i<=n;i++)
#define fod(i,n,m) for(int i=n;i>=m;i--)
#define fo1(i,m,n,k) for(int i=m;i<=n;i=i+k)
#define fod1(i,n,m,k) for(int i=n;i>=m;i=i-k)
#define fol(i,m,n) for(long long i=m;i<=n;i++)
#define fodl(i,n,m) for(long long i=n;i>=m;i--)
#define fo1l(i,m,n,k) for(long long i=m;i<=n;i=i+k)
#define fod1l(i,n,m,k) for(long long i=n;i>=m;i=i-k)
#define lb lower_bound
#define ub upper_bound
#define pii pair <int,int>
#define vii vector<pii>
#define ll long long
#define fi first
#define se second
#define si size()
#define pb push_back
#define ppb pop_back()
#define fr front()
#define et empty()
#define bg begin()
#define ub upper_bound
#define lb lower_bound
#define ed end()
#define el endl
#define EL cout << '\n';
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 5;
const int M = 1e3 + 5;
ll bit[16], ktra[1 << 15][16], val[1 << 15], indx[62];
int n, m, k, sz[1 << 15];
pii p[72];
vii adj[72];
void dfs(int v, int par){
    for(pii it : adj[v]){
        if(it.fi == par) continue;
        p[it.fi] = {v, it.se};
        dfs(it.fi, v);
    }
}
void solve(){
    cin >> n >> m >> k;
    fo(i, 0, n - 2){
        int a, b;
        cin >> a >> b;
        --a, --b;
        adj[a].pb({b, i}), adj[b].pb({a, i});
    }
    fo(i, 0, m - 1){
        int a, b;
        cin >> a >> b;
        --a, --b;
        dfs(a, a);
        while(b != a){
            bit[i] |= (1LL << (p[b].se));
            b = p[b].fi;
        }
    }
    indx[0] = 1;
    fo(i, 0, n - 1) indx[i + 1] = (indx[i] * k) % mod;
    ll ans = indx[n - 1];
    fo(mask, 1, (1 << m) - 1){
        int ind = __builtin_ctz(mask);
        int pr = mask - (1 << ind);
        ll edl = bit[ind], cur = edl;
        val[mask] = val[pr] | edl;
        fo(i, 0, sz[pr] - 1){
            if(ktra[pr][i] & edl) cur |= ktra[pr][i];
            else ktra[mask][sz[mask]++] = ktra[pr][i];
        }
        ktra[mask][sz[mask]++] = cur;
        int choice = sz[mask] + (n - 1 - __builtin_popcountll(val[mask]));
        int add = (__builtin_popcount(mask) & 1) ? -indx[choice] : indx[choice];
        ans = (ans + add + mod) % mod;
    }
    cout << ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

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