Submission #1113396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113396		fryingduc	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	11 ms	508 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif


const int maxn = 75;
const int mod = 1e9 + 7;
const int M = 20;

int n, m, k;
int qx[maxn], qy[maxn];
vector<int> g[maxn];
int fact[maxn], p[maxn];
int lca[maxn][maxn];
int h[maxn], par[maxn];
int eu[maxn], ev[maxn];

int lab[maxn];
struct dsu {
  int n;
  dsu() {}
  dsu(int n) : n(n) {
    memset(lab, -1, sizeof(lab));
  }
  int find(int u) {
    return lab[u] < 0 ? u : lab[u] = find(lab[u]);
  }
  void join(int u, int v) {
    u = find(u), v = find(v);
    if(u == v) return;
    if(lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
  }
} ds;
void pre_dfs(int u, int prev) {
  for(auto v:g[u]) {
    if(v == prev) continue;
    h[v] = h[u] + 1;
    par[v] = u;
    pre_dfs(v, u);
  }
}
int get_lca(int u, int v) {
  if(h[u] < h[v]) swap(u, v);
  while(h[u] != h[v]) {
    u = par[u];
  }
  if(u == v) return u;
  while(u != v) {
    u = par[u], v = par[v];
  }
  return u;
}
int add(int x, int y) {
  if(y < 0) y += mod;
  x = x + y;
  if(x >= mod) x -= mod;
  return x;
}
void solve() {
  cin >> n >> m >> k;
  for(int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
    
    eu[i] = u, ev[i] = v;
  }
  for(int i = 1; i <= m; ++i) {
    cin >> qx[i] >> qy[i];
  }
  pre_dfs(1, 0);
  for(int i = 1; i <= n; ++i) {
    for(int j = 1; j <= n; ++j) {
      lca[i][j] = get_lca(i, j);
    }
  }
  p[0] = 1;
  for(int i = 1; i <= n; ++i) {
    p[i] = 1ll * p[i - 1] * k % mod; 
  }
  int res = 0;
  for(int mask = 0; mask < (1 << m); ++mask) { 
    ds = dsu(n);
    for(int i = 0; i < m; ++i) {
      if(!(mask >> i & 1)) continue;
      int u = qx[i + 1], v = qy[i + 1];
      int l = lca[u][v];
      int x = (u == l ? v : u);
      while(u != l) {
        ds.join(u, x);
        u = par[u];
      }
      while(v != l) {
        ds.join(v, x);
        v = par[v];
      }
    }
    int cnt = 0;

    for(int i = 2; i <= n; ++i) {
      cnt += ds.find(i) == i;
    }
//    debug(mask, cnt, p[cnt]);
    if(__builtin_popcount(mask) & 1) {
      res = add(res, -p[cnt]);
    } else {
      res = add(res, p[cnt]);
    }
  }
  cout << res;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  fact[0] = 1;
  for(int i = 1; i < maxn; ++i) {
    fact[i] = 1ll * fact[i - 1] * i % mod;
  }

  solve();

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 65 / 65