oj.uz

Submission #1113396

# Submission time Handle Problem Language Result Execution time Memory
1113396 2024-11-16T14:05:25 Z fryingduc Šarenlist (COCI22_sarenlist) C++17
110 / 110
 11 ms 508 KB 
#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.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
65.0 / 65.0

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