oj.uz

Submission #703975

# Submission time Handle Problem Language Result Execution time Memory
703975 2023-03-01T07:48:31 Z willychan Šarenlist (COCI22_sarenlist) C++14
110 / 110
 18 ms 340 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds


vector<int> side[61];
int dep[61];
int pa[61];

void dfs(int cur,int p) {
    pa[cur]=p;
    dep[cur] = dep[p]+1;
    for(auto i : side[cur]) {
        if(!pa[i]) dfs(i,cur);
    }
}

int dsu[61];
int n;
void init() {
    for(int i=0; i<=n; i++) dsu[i] = i;
}

int query(int a) {
    if(dsu[a]==a) return a;
    dsu[a] = query(dsu[a]);
    return dsu[a];
}

void join(int a,int b) {
    a = query(a);
    b=  query(b);
    dsu[a]=b;
}
map<pair<int,int>,int> mp;

int mk(int a,int b) {
    return mp[make_pair(min(a,b),max(a,b))];
}

const int MOD = 1e9+7;
int m,k;
int main() {
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    cin>>m>>k;
    for(int i=1; i<n; i++) {
        int a,b;
        cin>>a>>b;
        side[a].push_back(b);
        side[b].push_back(a);
        mp[make_pair(min(a,b),max(a,b))]=i;
    }
    dfs(1,0);
    int pow[n+1];
    pow[0]=1;
    for(int i=1; i<=n; i++) {
        pow[i] = (1LL*pow[i-1]*k)%MOD;
    }
    vector<int> stuff[m];
    for(int i=0; i<m; i++) {
        int a,b;
        cin>>a>>b;
        if(dep[a]>dep[b]) swap(a,b);
        while(dep[b]>dep[a]) {
            stuff[i].push_back(mk(b,pa[b]));
            b = pa[b];
        }
        while(a!=b) {
            stuff[i].push_back(mk(a,pa[a]));
            stuff[i].push_back(mk(b,pa[b]));
            a = pa[a];
            b = pa[b];
        }
    }
    ll sameans = 0;

    for(int mask=1; mask<(1<<m); mask++) {
        init();
        for(int i=0; i<m; i++) {
            if((mask>>i)&1) {
                for(int j =1; j<stuff[i].size(); j++) {
                    join(stuff[i][j],stuff[i][j-1]);
                }
            }
        }
        int cnt = 0;
        for(int i=1; i<n; i++) {
            query(i);
            if(i==dsu[i]) {
                cnt++;
            }
        }
        if(__builtin_popcount(mask)%2) {
            sameans+=pow[cnt];
        } else {
            sameans-=pow[cnt];
        }
        sameans%=MOD;
        if(sameans<0) sameans+=MOD;

    }
    ll ans = pow[n-1];
    ans-=sameans;
    ans%=MOD;
    if(ans<0) ans+=MOD;
    cout<<ans<<"\n";


    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 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 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 1 ms 324 KB Output is correct
6 Correct 0 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 324 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 328 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 2 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #5
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 324 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 2 ms 324 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 328 KB Output is correct
20 Correct 1 ms 328 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 324 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 2 ms 212 KB Output is correct
25 Correct 2 ms 212 KB Output is correct
26 Correct 1 ms 212 KB Output is correct
27 Correct 9 ms 324 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 9 ms 324 KB Output is correct
31 Correct 3 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct
34 Correct 2 ms 212 KB Output is correct
35 Correct 5 ms 324 KB Output is correct
36 Correct 18 ms 324 KB Output is correct
37 Correct 8 ms 212 KB Output is correct