Submission #867938

#	Time	Username	Problem	Language	Result	Execution time	Memory
867938		epicci23	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	141 ms	604 KiB

Main

#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);
    set<int> s;
  	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);
        set<int> cur_s;
        while(depth[a]>depth[b]){
          s.insert(a);
          cur_s.insert(a);
          a=par[a];
        }
        while(a!=b){
          s.insert(a);
          s.insert(b);
          cur_s.insert(a);
          cur_s.insert(b);
          a=par[a];
          b=par[b];
        }
        int xd = *cur_s.begin();
        for(auto x:cur_s) dsu.unite(xd,x);
      }
  	}

  	int cur=1; 
    for(int i=2;i<=n;i++) if(!s.count(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 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 65 / 65