Submission #696636

#	Time	Username	Problem	Language	Result	Execution time	Memory
696636		Tuanlinh123	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	20 ms	2704 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

#define LOCALIO "C:/Users/admin/Documents/Code/"

const ll Mod=1e9+7;

ll binpow(ll a, ll k)
{
    ll ans=1;
    while (k)
    {
        if (k%2==1)
            ans=ans*a%Mod;
        a=a*a%Mod;
        k>>=1;
    }
    return ans;
}

vector <pll> A[100005];
pll req[100005];
pll pa[100005];
ll dep[100005];

ll Pa[100005], Rank[100005];

ll Find(ll i)
{
    if (Pa[i]!=i)
        Pa[i]=Find(Pa[i]);
    return Pa[i];
}

void Union(ll a, ll b)
{
    ll PA=Find(a), PB=Find(b);
    if (PA==PB) return;
    if (Rank[PA]<Rank[PB]) swap(PA, PB);
    if (Rank[PA]==Rank[PB]) Rank[PA]++;
    Pa[PB]=PA;
}

void dfs(ll u)
{
    for (pll child:A[u])
    {
        ll v=child.fi, idx=child.se;
        if (v==pa[u].fi)
            continue;
        pa[v]={u, idx};
        dep[v]=dep[u]+1;
        dfs(v);
    }
}

void update(ll u, ll v)
{
    ll x=-1;
    while (u!=v)
    {
        if (dep[u]<dep[v]) swap(u, v);
        if (x==-1) x=pa[u].se;
        else Union(x, pa[u].se);
        u=pa[u].fi;
    }
}

int main()
{
    #ifdef LOCAL
        freopen( LOCALIO "input.txt","r",stdin) ;
        freopen( LOCALIO "output.txt","w",stdout) ;
    #endif

    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
//	freopen("FIBONACCI.inp","r",stdin);
//	freopen("FIBONACCI.out","w",stdout);
    ll n, m, k; cin >> n >> m >> k;
    for (ll i=1; i<n; i++)
    {
        ll u, v; cin >> u >> v;
        A[u].pb({v, i});
        A[v].pb({u, i});
    }
    dfs(1);
    for (ll i=0; i<m; i++)
        cin >> req[i].fi >> req[i].se;
    ll ans=0;
    for (ll mask=0; mask<1<<m; mask++)
    {
        for (ll i=1; i<n; i++)
            Pa[i]=i, Rank[i]=0;
        for (ll i=0; i<m; i++)
            if (mask&1<<i)
                update(req[i].fi, req[i].se);
        ll cnt=0;
        for (ll i=1; i<n; i++)
            cnt+=Pa[i]==i;
        cnt=binpow(k, cnt);
        if (__builtin_popcount(mask)%2==0)
            ans+=cnt;
        else ans-=cnt;
        ans%=Mod; ans+=Mod; ans%=Mod;
    }
    cout << ans;
}

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