oj.uz

Submission #528636

# Submission time Handle Problem Language Result Execution time Memory
528636 2022-02-20T23:13:26 Z leaked Šarenlist (COCI22_sarenlist) C++14
110 / 110
 15 ms 332 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_innop ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const int M=1e9+7;
const int N=64+1;
void add(int &a,int b){
    a+=b;
    if(a>=M) a-=M;
    else if(a<0) a+=M;
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
int binpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=mult(ans,a);
        b>>=1;a=mult(a,a);
    }
    return ans;
}
vec<int> g[N];
int tt=0,tin[N],tout[N];
pii pr[N];
void dfs(int v,int p){
    tin[v]=tt++;
    for(auto &z : g[v]){
        if(z==p) continue;
        dfs(z,v);
//        cout<<"VGFD "<<v<<' '<<z<<endl;
        pr[z]={v,tin[z]};
    }
    tout[v]=tt-1;
}
bool is(int a,int b){
    return tin[a]<=tin[b]&&tout[a]>=tout[b];
}

struct dsu{
    int p[N];
    void make(int v){
        p[v]=v;
    }
    void init(){
        for(int i=0;i<N;i++) make(i);
    }
    int get(int v){
        return p[v]=(p[v]==v?v:get(p[v]));
    }
    bool mg(int a,int b){
        a=get(a),b=get(b);
        if(a==b) return 0;
        p[a]=b;
        return 1;
    }
};
signed main(){
    fast_innop;
    int n,m,k;
    cin>>n>>m>>k;
    vec<int>pk(n+1,1);
    for(int i=1;i<=n;i++) pk[i]=mult(pk[i-1],k);
    for(int i=1;i<n;i++){
        int v,u;
        cin>>v>>u;--v;--u;
        g[v].pb(u);g[u].pb(v);
    }
    dfs(0,0);
    vec<int>a(m),b(m);
    vec<ll>have(m);
    for(int i=0;i<m;i++){
        cin>>a[i]>>b[i];--a[i];--b[i];
        int v=a[i];
        while(!is(v,b[i])){
            have[i]|=pw(v);
            v=pr[v].f;
        }
        v=b[i];
        while(!is(v,a[i])){
            have[i]|=pw(v);
            v=pr[v].f;
        }
    }
    dsu ds;
    int ans=0;
    for(int mask=0;mask<pw(m);mask++){
        ds.init();
        int cnt=0;
        ll wt=0;
        vec<int>vc;
        for(int i=0;i<m;i++){
            if(pw(i)&mask){
                for(auto &z : vc){
                    if(have[i]&have[z])
                        ds.mg(i,z);
                }
                wt|=have[i];
                vc.pb(i);
            }
        }
        vec<int> cntt(n,0);
//        for(int i=0;i<m;i++){
//            cntt[ds.get(i)]++;
////            cout<<i<<' '<<ds.get(i)<<endl;
//        }
        for(auto &i : vc){
            if(i==ds.get(i)){
                ++cnt;
            }
        }
        int ways=pk[cnt+(n-1-__builtin_popcountll(wt))];
//        cout<<mask<<' '<<ways<<' '<<cnt<<' '<<n-1-__builtin_popcountll(wt)<<'\n';
        if(__builtin_popcount(mask)%2) add(ans,-ways);
        else add(ans,ways);
    }
    cout<<ans;
    return 0;
}
/*
7
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 312 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 316 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 320 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 4 ms 204 KB Output is correct
6 Correct 3 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #5
65.0 / 65.0

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