oj.uz

Submission #1107703

# Submission time Handle Problem Language Result Execution time Memory
1107703 2024-11-02T02:44:50 Z thangdz2k7 Šarenlist (COCI22_sarenlist) C++17
110 / 110
 16 ms 508 KB 
// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 70;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

namespace MODINT {
struct barrett {
    unsigned int _m;
    unsigned long long im;
    explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
    unsigned int umod() const { return _m; };
    unsigned int mul(unsigned int a, unsigned int b) const {
        unsigned long long z = a; z *= b;
        unsigned long long x = (unsigned long long)(((unsigned __int128) z * im) >> 64);
        unsigned long long y = x * _m;
        return (unsigned int)(z - y + (z < y ? _m : 0));
    }
};
template <class T> T invGeneral(T a, T b) {
    a %= b;
    if (!a) return b == 1 ? 0 : -1;
    T x = invGeneral(b, a);
    return x == -1 ? -1 : ((1 - 1LL * b * x) / a + b) % b;
}
template <int m, enable_if_t<1 <= m>* = nullptr>
struct static_modint {
using mint = static_modint;
public:
    static constexpr int mod() { return m; }
    static mint raw(int v) {
        mint x; x.v = v;
        return x;
    }
    static_modint(): v(0) {}
    template <class T> static_modint(T x) {
        int y;
        if (x < 0) {
            if (x < -mod()) y = x % mod();
            else y = x;
            if (y < 0) y += mod();
        } else {
            if (x < mod()) y = x;
            else y = x % mod();
        }
        v = y;
    }
    unsigned int val() const { return v; }
    unsigned int operator () () const { return v; }
    mint & operator ++ () { if (++v == umod()) v = 0; return *this; }
    mint & operator -- () { if (!v) v = umod(); --v; return *this; }
    mint operator ++ (int) { mint old = *this; ++*this; return old; }
    mint operator -- (int) { mint old = *this; --*this; return old; }
    mint operator + () { return *this; }
    mint operator - () { return raw(!v ? 0 : umod() - v); }
    mint & operator += (const mint &rhs) { v += rhs.v; if (v >= umod()) v -= umod(); return *this; }
    mint & operator -= (const mint &rhs) { v -= rhs.v; if (v >= umod()) v += umod(); return *this; }
    mint & operator *= (const mint &rhs) {
        unsigned long long z = v; z *= rhs.v; v = z % umod();
        return *this;
    }
    mint & operator /= (const mint &rhs) { return *this *= rhs.inv(); }
    friend mint operator + (const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
    friend mint operator - (const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
    friend mint operator * (const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
    friend mint operator / (const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
    mint pow(long long n) const {
        assert(0 <= n);
        mint res = 1, a = *this;
        for (; n; n >>= 1, a *= a) if (n & 1) res *= a;
        return res;
    }
    mint inv() const {
        int i = invGeneral((int) v, mod());
        assert(~i);
        return i;
    }
    friend bool operator == (const mint& lhs, const mint& rhs) { return lhs.v == rhs.v; }
    friend bool operator != (const mint& lhs, const mint& rhs) { return lhs.v != rhs.v; }
    friend ostream & operator << (ostream &out, const mint &x) { return out << x.v; }
    friend istream & operator >> (istream &in, mint &x) { long long a; in >> a; x = a; return in; }
    explicit operator bool() const { return v; }
    explicit operator int() const { return v; }
private:
    unsigned int v;
    static constexpr unsigned int umod() { return m; }
};
template <int id> struct dynamic_modint {
using mint = dynamic_modint;
public:
    static int mod() { return (int) bt.umod(); }
    static void set_mod(int m) {
        assert(1 <= m);
        bt = barrett(m);
    }
    static mint raw(int v) {
        mint x; x.v = v;
        return x;
    }
    dynamic_modint(): v(0) {}
    template <class T> dynamic_modint(T x) {
        int y;
        if (x < 0) {
            if (x < -mod()) y = x % mod();
            else y = x;
            if (y < 0) y += mod();
        } else {
            if (x < mod()) y = x;
            else y = x % mod();
        }
        v = y;
    }
    unsigned int val() const { return v; }
    unsigned int operator () () const { return v; }
    mint & operator ++ () { if (++v == umod()) v = 0; return *this; }
    mint & operator -- () { if (!v) v = umod(); --v; return *this; }
    mint operator ++ (int) { mint old = *this; ++*this; return old; }
    mint operator -- (int) { mint old = *this; --*this; return old; }
    mint operator + () { return *this; }
    mint operator - () { return raw(!v ? 0 : umod() - v); }
    mint & operator += (const mint &rhs) { v += rhs.v; if (v >= umod()) v -= umod(); return *this; }
    mint & operator -= (const mint &rhs) { v -= rhs.v; if (v >= umod()) v += umod(); return *this; }
    mint & operator *= (const mint &rhs) {
        v = bt.mul(v, rhs.v);
        return *this;
    }
    mint & operator /= (const mint &rhs) { return *this *= rhs.inv(); }
    friend mint operator + (const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }
    friend mint operator - (const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }
    friend mint operator * (const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }
    friend mint operator / (const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }
    mint pow(long long n) const {
        assert(0 <= n);
        mint res = 1, a = *this;
        for (; n; n >>= 1, a *= a) if (n & 1) res *= a;
        return res;
    }
    mint inv() const {
        int i = invGeneral((int) v, mod());
        assert(~i);
        return i;
    }
    friend bool operator == (const mint& lhs, const mint& rhs) { return lhs.v == rhs.v; }
    friend bool operator != (const mint& lhs, const mint& rhs) { return lhs.v != rhs.v; }
    friend ostream & operator << (ostream &out, const mint &x) { return out << x.v; }
    friend istream & operator >> (istream &in, mint &x) { long long a; in >> a; x = a; return in; }
    explicit operator bool() const { return v; }
    explicit operator int() const { return v; }
private:
    unsigned int v;
    static barrett bt;
    static unsigned int umod() { return bt.umod(); }
};
template <int id> barrett dynamic_modint<id>::bt(998244353);
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint <-1>;
using Modular = modint1000000007; // set mod
} using namespace MODINT;

// remember to set mod

struct DSU{
    vi par;

    DSU(int n){
        par.resize(n);
        for (int i = 0; i < n; ++ i) par[i] = i;
    }

    int find(int u){
        if (u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    bool check(int u, int v){
        return find(u) == find(v);
    }

    void joint(int u, int v){
        u = find(u); v = find(v);
        par[u] = v;
    }
};

int n, m, k, dep[N], par[N], x[N], y[N];
vector <int> adj[N];

void dfs(int u = 0, int p = n){
    par[u] = p;
    for (int v : adj[u]) if (v ^ p){
        dep[v] = dep[u] + 1;
        dfs(v, u);
    }
}

Modular pow_k[N];

#define Mask(i)  (1 << (i))
#define Bit(x, i)  ((x) >> (i) & 1)
#define bp __builtin_popcount
#define bpll __builtin_popcountll

void solve(){
    cin >> n >> m >> k;
    for (int i = 0; i < n - 1; ++ i){
        int u, v; cin >> u >> v;
        -- u, -- v;
        adj[u].pb(v); adj[v].pb(u);
    }
    dep[0] = 1; dfs();
    for (int i = 0; i < m; ++ i) {
        cin >> x[i] >> y[i];
        -- x[i], -- y[i];
    }

    pow_k[0] = 1;
    for (int i = 1; i < n; ++ i) pow_k[i] = pow_k[i - 1] * k;

    int mx = (1 << m);
    Modular ans = 0;
    for (int mask = 0; mask < mx; ++ mask){
        DSU T(n);
        for (int i = 0; i < m; ++ i) if (Bit(mask, i)){
            int u = x[i], v = y[i], last = -1;
            while (u != v){
                if (dep[u] < dep[v]) swap(u, v);
                if (last > -1) T.joint(last, u);
                last = u, u = par[u];
            }
        }

        int cnt = 0;
        for (int i = 1; i < n; ++ i) cnt += (T.find(i) == i);
        if (bp(mask) % 2) ans -= pow_k[cnt];
        else ans += pow_k[cnt];
    }

    cout << ans;
}

int main(){
    if (fopen("coloring.inp", "r")){
        freopen("coloring.inp", "r", stdin);
        freopen("coloring.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message

Main.cpp:18:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
Main.cpp:18:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
Main.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
Main.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
Main.cpp: In function 'int main()':
Main.cpp:258:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  258 |         freopen("coloring.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:259:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  259 |         freopen("coloring.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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 336 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 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 1 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 508 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 2 ms 336 KB Output is correct
6 Correct 3 ms 504 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 336 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 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 1 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 508 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 2 ms 336 KB Output is correct
25 Correct 3 ms 504 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 376 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 8 ms 336 KB Output is correct
31 Correct 3 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 460 KB Output is correct
36 Correct 16 ms 336 KB Output is correct
37 Correct 8 ms 504 KB Output is correct