oj.uz

Submission #867937

# Submission time Handle Problem Language Result Execution time Memory
867937 2023-10-29T21:23:38 Z epicci23 Šarenlist (COCI22_sarenlist) C++17
35 / 110
 3 ms 516 KB 
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

constexpr int MOD = 1e9 + 7;

int mult(int a,int b){
  a%=MOD;b%=MOD;
  if(a*b>=MOD) return (a*b)%MOD;
  return a*b;
}

int eks(int a,int b){
  a%=MOD;b%=MOD;
  if(a<b) return (a-b)+MOD;
  return a-b;
}

int add(int a,int b){
  a%=MOD;b%=MOD;
  if(a+b>=MOD) return (a+b)%MOD;
  return a+b;
}



struct DSU{
  int comp,comp2;
  vector<int> par;
  vector<int> siz;
  vector<int> vis;
  DSU(int n){
    comp=n;
    comp2=0;
    par.resize(n+5);
    vis.assign(n+5,0);
    siz.assign(n+5,1);
    iota(all(par),0);
  }

  int find(int a){
  	if(par[a]==a) return a;
  	return par[a]=find(par[a]);
  }

  void unite(int a,int b){
    a=find(a),b=find(b);
    if(a==b) return;
    if(!vis[a]){
  	  vis[a]=1;
  	  comp2++;
  	}
  	if(!vis[b]){
  	  vis[b]=1;
  	  comp2++;
  	}
    comp--;
    comp2--;
    if(siz[a]>siz[b]) swap(a,b);
    siz[b]+=siz[a];
    par[a]=b;
  }
};

vector<int> v[65];
int par[65];
int depth[65];

void dfs(int c,int p,int d){
  par[c]=p;
  depth[c]=d;
  for(int x:v[c]){
  	if(x==p) continue;
  	dfs(x,c,d+1);
  }
} 



void solve(){
  int n,m,k;
  cin >> n >> m >> k;

  int ans=0;
  
  int pre[n+5];
  pre[0]=1;
  for(int i=1;i<n+5;i++) pre[i]=mult(pre[i-1],k);

  array<int,2> ar[m+5];

  for(int i=1;i<n;i++){
  	int a,b;
  	cin >> a >> b;
  	v[a].pb(b);
  	v[b].pb(a);
  }
  
  dfs(1,0,0);

  for(int i=0;i<m;i++){
  	int a,b;
  	cin >> a >> b;
  	ar[i]={a,b};
  }
 
  for(int mask=0;mask<(1LL<<m);mask++){

    DSU dsu(n);
    vector<int> vim(n+5,0);
  	for(int j=0;j<m;j++){
  	  if(mask>>j&1){
        int a = ar[j][0];
        int b = ar[j][1];
        if(depth[a]<depth[b]) swap(a,b);
        while(depth[a]>depth[b]){
          if(par[a]!=b) dsu.unite(a,par[a]);
          vim[a]=1;
          a=par[a];
        }
        while(a!=b){
          if(par[a]!=par[b]) dsu.unite(a,par[a]);
          else dsu.unite(a,b);
          vim[a]=1;
          a=par[a];
          if(par[a]!=par[b]) dsu.unite(b,par[b]);
          vim[b]=1;
          b=par[b];
        }
      }
  	}

  	int cur=1; 
    for(int i=2;i<=n;i++) if(!vim[i]) cur=mult(cur,k);
    cur=mult(cur,pre[dsu.comp2]); 

    //cout << mask << " " << cur << " " << dsu.comp2 << endl;

  	if(__builtin_popcountll(mask)&1) ans=eks(ans,cur);
  	else ans=add(ans,cur);
  }

  cout << ans << endl;
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 516 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 3 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Incorrect 0 ms 348 KB Output isn't correct
22 Halted 0 ms 0 KB -