Submission #696676

#	Time	Username	Problem	Language	Result	Execution time	Memory
696676		Hiennoob123	Šarenlist (COCI22_sarenlist)	C++14	110 / 110	19 ms	592 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const ll mod = 1e9+7;
ll n, m, k;
ll val[(1<<15)];
vector<pll> T[100];
vector<ll> Edge[20];
bool has[100];
ll s, t, type;
void dfs(ll v, ll par)
{
    if(v==t) has[v] = 1;
    for(auto u: T[v])
    {
        if(u.fi==par) continue;
        dfs(u.fi, v);
        if(has[u.fi])
        {
            has[v] = 1;
        }
    }
    //cout << has[3] << "\n";
    //cout << v << " " << has[v] << "\n";
    if(has[v])
    {
        for(auto u: T[v])
        {
            if(u.fi==par) Edge[type].push_back(u.se);
        }
    }
}
ll par[100], sz[100];
ll find_par(ll v)
{
    if(par[v]==v) return v;
    else return par[v] = find_par(par[v]);
}
void Merge(ll u, ll v)
{
    u = find_par(u); v = find_par(v);
    if(u==v) return;
    if(sz[u]<=sz[v])
    {
        sz[v]+=sz[u];
        par[u] = v;
    }
    else
    {
        sz[u]+=sz[v];
        par[v] = u;
    }
}
ll bin_pow(ll a, ll b)
{
    ll value = 1;
    while(b>0)
    {
        if(b&1) value = (value*a)%mod;
        a = (a*a)%mod;
        b>>=1;
    }
    return value;
}
void solve_num(ll num)
{
    for(int i = 1; i<= n-1; i++)
    {
        par[i] = i;
        sz[i] = 1;
    }
    for(int i = 0; i< m; i++)
    {
        if((num&(1<<i))==0) continue;
        for(int j = 1; j< Edge[i].size(); j++)
        {
            Merge(Edge[i][j], Edge[i][j-1]);
        }
    }
    ll tong = 0;
    for(int i = 1; i<= n; i++)
    {
        if(par[i]==i) tong++;
    }
    val[num] = bin_pow(k , tong);
}
void solve()
{
    cin >> n >> m >> k;
    for(int i = 1; i< n; i++)
    {
        ll a, b; cin >> a >> b;
        T[a].push_back(mp(b, i));
        T[b].push_back(mp(a, i));
    }
    for(int i = 0; i< m; i++)
    {
        cin >> s >> t;
        for(int j = 1; j<= n; j++) has[j] = 0;
        type = i;
        dfs(s, 0);
    }
    ll ans = 0;
    for(int i = 0; i< (1<<m); i++)
    {
        solve_num(i);
        //cout << i << " " << val[i] << "\n";
        if(__builtin_popcount(i)%2==0)
        {
            ans = (ans+val[i])%mod;
        }
        else
        {
            ans = (ans-val[i])%mod;
        }
    }
    ans %= mod;
    if(ans<0) ans+= mod;
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(NULL) ; cin.tie(nullptr) ; cout.tie(nullptr);
    //freopen("B.inp","r",stdin);
    ll test_case = 1;
    while(test_case--)
    {
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'void solve_num(long long int)':
Main.cpp:80:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int j = 1; j< Edge[i].size(); j++)
      |                        ~^~~~~~~~~~~~~~~~

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