oj.uz

Submission #1107705

# Submission time Handle Problem Language Result Execution time Memory
1107705 2024-11-02T02:55:23 Z tuannm Šarenlist (COCI22_sarenlist) C++17
110 / 110
 11 ms 508 KB 
#include<bits/stdc++.h>
#define ii pair<int, int>
#define ll pair<long long, long long>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod[2] = {1000000007, 998244353};
const int N = 1e2 + 1;
const string NAME = "coloring";
int n, m;
vector<int> adj[N];
int p[N], col[N], d[N], pa[N];
ii z[N];

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

Modular pk[N], k;

int find_set(int u){
    if(u == pa[u])
        return u;

    return pa[u] = find_set(pa[u]);
}

void join_set(int u, int v){
    u = find_set(u);
    v = find_set(v);

    if(u == v)
        return;

    pa[v] = u;
}

void inp(){
    cin >> n >> m >> k;

    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;

        adj[u].pb(v);
        adj[v].pb(u);
    }

    for(int i = 0; i < m; ++i)
        cin >> z[i].fi >> z[i].se;
}

void DFS(int u = 1){
    for(int v : adj[u]){
        if(v == p[u])
            continue;

        d[v] = d[u] + 1;
        p[v] = u;
        DFS(v);
    }
}

void solve(){
    DFS();
    Modular ans = 0;
    pk[0] = 1;

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

    for(int mask = 0; mask < (1 << m); ++mask){
        for(int i = 2; i <= n; ++i)
            col[i] = -1;

        for(int i = 0; i < m; ++i)
            pa[i] = i;

        for(int i = 0; i < m; ++i)
            if((mask >> i) & 1){
                auto [u, v] = z[i];

                while(u != v){
                    if(d[u] < d[v])
                        swap(u, v);

                    if(col[u] != -1)
                        join_set(i, col[u]);
                    col[u] = i;

                    u = p[u];
                }
            }

        set<int> ss;
        for(int i = 0; i < m; ++i)
            if((mask >> i) & 1)
                ss.insert(find_set(i));

        int cnt = ss.size();

        for(int i = 2; i <= n; ++i)
            cnt += (col[i] == -1);

        if(__builtin_popcount(mask) & 1)
            ans -= pk[cnt];
        else
            ans += pk[cnt];
    }

    cout << ans;
}

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

    if(fopen((NAME + ".inp").c_str(), "r")){
        freopen((NAME + ".inp").c_str(), "r", stdin);
        freopen((NAME + ".out").c_str(), "w", stdout);
    }

    inp();
    solve();
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:273:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  273 |         freopen((NAME + ".inp").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:274:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  274 |         freopen((NAME + ".out").c_str(), "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 348 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 504 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 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 504 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 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 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 348 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 504 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 2 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 504 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 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 5 ms 336 KB Output is correct
28 Correct 1 ms 508 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 7 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 1 ms 336 KB Output is correct
35 Correct 3 ms 336 KB Output is correct
36 Correct 11 ms 336 KB Output is correct
37 Correct 6 ms 336 KB Output is correct