Submission #1107693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107693		haianhnguyen08102007	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	29 ms	508 KiB

Main

#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 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 65 / 65