Submission #878647

#	Time	Username	Problem	Language	Result	Execution time	Memory
878647		noiaint	Šarenlist (COCI22_sarenlist)	C++17	110 / 110	43 ms	460 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 100 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, m, k;
vector<pair<int, int> > adj[N];
pair<int, int> path[N];
int par[N], par_id[N];
int e[N];
int cnt = 0;

int getpar(int x) {
    return e[x] < 0 ? x : e[x] = getpar(e[x]);
}
bool unite(int x, int y) {
    x = getpar(x);
    y = getpar(y);
    if (x == y) return false;
    if (-e[x] < -e[y]) swap(x, y);
    e[x] += e[y];
    e[y] = x;
    --cnt;
    return true;
}

void dfs(int u, int p) {
    for (auto [v, id] : adj[u]) if (v != p) {
        par[v] = u;
        par_id[v] = id;
        dfs(v, u);
    }
}

void update(int x, int y) {
    par[x] = x;
    dfs(x, 0);
    for (int u = y; par[u] != x; u = par[u]) {
        unite(par_id[u], par_id[par[u]]);
    }
}

void process() {
    cin >> n >> m >> k;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v, i);
        adj[v].emplace_back(u, i);
    }
    for (int i = 0; i < m; ++i) cin >> path[i].fi >> path[i].se;
        
    int ans = 0;
    for (int mask = 0; mask < bit(m); ++mask) {
        memset(e, -1, sizeof e);
        cnt = n - 1;

        for (int i = 0; i < m; ++i) if (getbit(mask, i)) {
            update(path[i].fi, path[i].se);
        }

        int cur = 1;
        for (int i = 0; i < cnt; ++i) cur = 1LL * cur * k % mod;

        debug(cur, cnt);
        int sgn = popcount(mask) & 1 ? -1 : 1;
        add(ans, sgn * cur);
    }

    cout << ans;
}

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

    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    #endif

    int tc = 1;
    // cin >> tc;
    
    while (tc--) {
        process();
    }

    return 0;
}

/*

*/  

Compilation message (stderr)

Main.cpp: In function 'void process()':
Main.cpp:8:20: warning: statement has no effect [-Wunused-value]
    8 | #define debug(...) 42
      |                    ^~
Main.cpp:104:9: note: in expansion of macro 'debug'
  104 |         debug(cur, cnt);
      |         ^~~~~

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