Submission #671277

#	Time	Username	Problem	Language	Result	Execution time	Memory
671277		neki	Šarenlist (COCI22_sarenlist)	C++14	110 / 110	29 ms	308 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define vc vector

using namespace std;
struct dsu{
    ll n, cc;
    vc<ll> d;
    dsu(ll n_):n(n_){d.resize(n); for(ll i=0;i<n;++i) d[i]=i;cc=n;}
    ll fnd(ll u){assert(u>=0 && u<n);return (u==d[u])?u:d[u]=fnd(d[u]);}
    void join(ll a, ll b){assert(a>=0 && a<n);assert(b>=0 && b<n);ll pa=fnd(a), pb=fnd(b);if(pa!=pb) d[pa]=pb, --cc;}
};
const ll mod=1e9+7;
ll fpow(ll b, ll e){ll ret=1;for(;e;e/=2, b=b*b%mod, ret%=mod)if(e&1)ret*=b;return ret;}
int main() {
    ll n, m, k;cin >> n >> m >> k;
    
    vc<vc<pair<ll, ll>>> edg(n+1);
    for(ll i=0;i<n-1;++i){
        ll a, b;cin >> a >> b;
        edg[a].emplace_back(b, i);
        edg[b].emplace_back(a, i);
    }
    vc<ll> s(m), e(m);
    for(ll i=0;i<m;++i) cin >> s[i] >> e[i];
    
    vc<vc<ll>> ued(m);
    for(ll i=0;i<m;++i){
        function<ll (ll, ll)> dfs=[&](ll u, ll p){
            if(u==e[i]) return 1LL;
            for(auto v: edg[u]) if(v.first!=p){
                if(dfs(v.first, u)){ ued[i].push_back(v.second); return 1LL;}
            }
            return 0LL;
        };
        dfs(s[i], -1);
        //for(auto ed: ued[i]) cout <<ed <<" "; cout << endl;
    }
    ll ans=0;
    for(ll b=0;b<(1<<m);++b){
        dsu D(n-1);
        for(ll i=0;i<m;++i) if(b&(1<<i)){
            for(ll j=0;j+1<ued[i].size();++j) D.join(ued[i][j], ued[i][j+1]);
        }
        //cout << D.cc<<endl;
        ans+=mod+((__builtin_popcountll(b)%2)? -1LL:1LL) * fpow(k, D.cc); ans%=mod;
    }
    cout << ans << endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:43:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(ll j=0;j+1<ued[i].size();++j) D.join(ued[i][j], ued[i][j+1]);
      |                        ~~~^~~~~~~~~~~~~~

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