oj.uz

Submission #1107693

# Submission time Handle Problem Language Result Execution time Memory
1107693 2024-11-02T01:42:01 Z haianhnguyen08102007 Šarenlist (COCI22_sarenlist) C++17
110 / 110
 29 ms 508 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int N = 1e6+2;
const int mod = 1e9 + 7;
const ll inf = 1e17;

int n, m, k, p[100], lvl[100], viz[100];
vector<int>G[100];
vector<int>eq[100];
pii v[100];

void dfs (int nod, int par) {
      p[nod] = par;
      lvl[nod] = lvl[par] + 1;
      for (auto it : G[nod]) {
        if (it != par)
          dfs(it, nod);
      }
}

void dfs2 (int x) {
      viz[x]=1;
      for (auto it : eq[x])
        if (!viz[it])
          dfs2(it);
}

int calc (vector<pii>drum) {
      for (auto [x, y] : drum) {
         if (lvl[x] < lvl[y])
          swap(x, y);
        int xx = x;
        while (x != y) {
          if (lvl[x] < lvl[y])
            swap(x, y);
          eq[x].push_back(xx);
          eq[xx].push_back(x);
          x = p[x];
        }
      }
      int ans = 1;
      for (int i = 2; i <= n; i++) {
        if (!viz[i]) {
          ans = 1ll * ans * k % mod;
          dfs2(i);
        }
      }
      for (int i = 1; i <= n; i++) {
        eq[i].clear();
        viz[i] = 0;
      }
      return ans;
}


int main ()
{
      ios_base::sync_with_stdio(false);
      cin.tie(0); cout.tie(0);

//      freopen("coloring.inp", "r", stdin);
//      freopen("coloring.out", "w", stdout);

      cin >> n >> m >> k;
      for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
      }
      for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        v[i] ={x, y};
      }
      dfs(1, 0);
      int ans = 1;
      for (int i = 1; i < n; i++)
        ans = 1ll * ans * k % mod;
      for (int mask = 1; mask < (1 << m); mask++) {
        vector<pii>aux;
        for (int i = 0; i < m; i++)
          if (mask & (1 << i))
            aux.push_back(v[i]);
        if (__builtin_popcount(mask) % 2)
          ans = (ans - calc(aux) + mod) % mod;
        else
          ans = (ans + calc(aux)) % mod;
      }
      cout << ans;
      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 508 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 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 336 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 336 KB Output is correct
5 Correct 3 ms 336 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 4 ms 336 KB Output is correct
6 Correct 5 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 508 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 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 336 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 336 KB Output is correct
17 Correct 3 ms 336 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 4 ms 336 KB Output is correct
25 Correct 5 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 17 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 14 ms 508 KB Output is correct
31 Correct 5 ms 504 KB Output is correct
32 Correct 2 ms 336 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 2 ms 468 KB Output is correct
35 Correct 8 ms 336 KB Output is correct
36 Correct 29 ms 336 KB Output is correct
37 Correct 13 ms 336 KB Output is correct