oj.uz

Submission #671277

# Submission time Handle Problem Language Result Execution time Memory
671277 2022-12-12T16:38:52 Z neki Šarenlist (COCI22_sarenlist) C++14
110 / 110
 29 ms 308 KB 
#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

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.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 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 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 0 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 212 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 0 ms 212 KB Output is correct
3 Correct 1 ms 220 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 220 KB Output is correct
6 Correct 1 ms 216 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 216 KB Output is correct
2 Correct 1 ms 216 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 216 KB Output is correct
6 Correct 3 ms 304 KB Output is correct
7 Correct 0 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 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 220 KB Output is correct
16 Correct 1 ms 308 KB Output is correct
17 Correct 1 ms 220 KB Output is correct
18 Correct 1 ms 216 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 216 KB Output is correct
21 Correct 1 ms 216 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 2 ms 216 KB Output is correct
25 Correct 3 ms 304 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 9 ms 304 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 300 KB Output is correct
30 Correct 10 ms 308 KB Output is correct
31 Correct 3 ms 300 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 6 ms 212 KB Output is correct
36 Correct 29 ms 212 KB Output is correct
37 Correct 12 ms 212 KB Output is correct