結果

問題 No.2494 Sum within Components
ユーザー idat_50me
提出日時 2023-10-06 21:46:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 53 ms / 2,000 ms
コード長 12,844 bytes
コンパイル時間 1,872 ms
コンパイル使用メモリ 205,884 KB
最終ジャッジ日時 2025-02-17 04:58:09
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// -------------------- main code begins at #263 -------------------- //
#include <bits/stdc++.h>
using namespace std;
template<typename T, typename U> using vp = vector<pair<T, U>>;
template<typename T> using pque = priority_queue<T>;
template<typename T> using lpque = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename U> using umap = unordered_map<T, U>;
template<typename T> using uset = unordered_set<T>;
#define pque_op(T, op) (priority_queue<T, vector<T>, decltype(op)>(op))
#define set_op(T, op, ...) (set<T, decltype(op)>(__VA_OPT__(__VA_ARGS__, ) op))
using lint = long long;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
using pil = pair<int, lint>;
using pli = pair<lint, int>;
using vint = vector<int>;
using vlint = vector<lint>;
using vpint = vector<pint>;
using vplint = vector<plint>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vbl = vector<bool>;
using qint = queue<int>;
using qlint = queue<lint>;
constexpr double PI = 3.141592653589793;
constexpr int INTINF = (1 << 30) - 1;
constexpr lint LLINF = (1LL << 62) - 1;
constexpr int MPRIME = 1000000007;
constexpr int MPRIME9 = 998244353;
constexpr lint MMPRIME = (1LL << 61) - 1;
constexpr char newl = '\n';
#define len length()
#define empb(...) emplace_back(__VA_ARGS__)
#define fi first
#define se second
#define get_rep(_1, _2, _3, func, ...) func
#define rep(i, ...) get_rep(__VA_ARGS__, rep3, rep2, rep1)(i, __VA_ARGS__)
#define rep1(i, N) for(int i = 0; i < (N); i++)
#define rep2(i, s, t) for(int i = (s); i < (t); i++)
#define rep3(i, s, t, a) for(int i = (s); i < (t); i += (a))
#define get_rrep(_1, _2, _3, func, ...) func
#define rrep(i, ...) get_rrep(__VA_ARGS__, rrep3, rrep2, rrep1)(i, __VA_ARGS__)
#define rrep1(i, N) for(int i = (N); i >= 0; i--)
#define rrep2(i, s, t) for(int i = (s); i >= (t); i--)
#define rrep3(i, s, t, a) for(int i = (s); i >= (t); i -= (a))
#define forbit(bit, k) for(int bit = 0; bit < (1 << (k)); bit++)
#define forsubset(bit, orig_bit)                                                                        \
    for(int bit = (orig_bit), _cnt = 0; (_cnt += (bit == (orig_bit))) < 2; --bit &= (orig_bit))
#define bitpop(bit, k) (((bit) >> (k)) & 1)
#define all(name) name.begin(), name.end()
#define rall(name) name.rbegin(), name.rend()
#define gsort(vbeg, vend) sort(vbeg, vend, greater<>())
#define dbg(x) cerr << #x << ": " << x << '\n';
inline int popcnt(lint bit) {
    return __builtin_popcountll(bit);
}
template<class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline void init(vector<T> &v) {
    for(auto &a : v) cin >> a;
}
template<class T, class U> inline void init(vector<pair<T, U>> &v) {
    for(auto &a : v) cin >> a.first >> a.second;
}
template<class T> inline void init(vector<T> &v, int n) {
    v.resize(n);
    for(auto &a : v) cin >> a;
}
template<class T1, class T2> inline void init(vector<T1> &v1, vector<T2> &v2, int n) {
    v1.resize(n);
    v2.resize(n);
    for(int i = 0; i < n; i++) cin >> v1[i] >> v2[i];
}
template<class T1, class T2, class T3>
inline void init(vector<T1> &v1, vector<T2> &v2, vector<T3> &v3, int n) {
    v1.resize(n);
    v2.resize(n);
    v3.resize(n);
    for(int i = 0; i < n; i++) cin >> v1[i] >> v2[i] >> v3[i];
}
template<class T, class U> inline void init(vector<pair<T, U>> &v, int n) {
    v.resize(n);
    for(auto &a : v) cin >> a.first >> a.second;
}
template<class T> inline void init(vector<T> &v, int n, const T &c) {
    v.resize(n);
    for(auto &a : v) {
        cin >> a;
        a += c;
    }
}
template<class T1, class T2>
inline void init(vector<T1> &v1, vector<T2> &v2, int n, const T1 &c1, const T2 &c2) {
    v1.resize(n);
    v2.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> v1[i] >> v2[i];
        v1[i] += c1;
        v2[i] += c2;
    }
}
template<class T1, class T2, class T3>
inline void
init(vector<T1> &v1, vector<T2> &v2, vector<T3> &v3, int n, const T1 &c1, const T2 &c2, const T3 &c3) {
    v1.resize(n);
    v2.resize(n);
    v3.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> v1[i] >> v2[i] >> v3[i];
        v1[i] += c1;
        v2[i] += c2;
        v3[i] += c3;
    }
}
template<class T, class U> inline void init(vector<pair<T, U>> &v, int n, T &c1, U &c2) {
    v.resize(n);
    for(auto &a : v) {
        cin >> a.first >> a.second;
        a.first += c1;
        a.second += c2;
    }
}
inline void out() {
    cout << newl;
}
template<class T> inline void out(T a) {
    cout << a << '\n';
}
template<class T, class... U> inline void out(T a, U... lst) {
    cout << a << " ";
    out(forward<U>(lst)...);
}
template<class T> inline void out(vector<T> &v) {
    for(int i = 0; i < v.size(); i++) cout << v[i] << (i == v.size() - 1 ? '\n' : ' ');
    cout << flush;
}
template<class N> void resiz(N n) {}
template<class N, class T, class... U> void resiz(N n, T &&hd, U &&...tl) {
    hd.resize(n);
    resiz(n, forward<U>(tl)...);
}
bool Yes(bool b = true) {
    cout << (b ? "Yes" : "No") << newl;
    return b;
}
bool YES(bool b = true) {
    cout << (b ? "YES" : "NO") << newl;
    return b;
}
bool No(bool b = true) {
    if(!b) return false;
    cout << "No" << newl;
    return true;
}
bool NO(bool b = true) {
    if(!b) return false;
    cout << "NO" << newl;
    return true;
}
template<typename T> struct v2d {
private:
    vector<vector<T>> m;
public:
    v2d() {}
    v2d(int h, int w) : m(h, vector<T>(w)) {}
    v2d(int h, int w, const T &init) : m(h, vector<T>(w, init)) {}
    v2d(const initializer_list<initializer_list<T>> m_init) : m(m_init.begin(), m_init.end()) {}
    void assign(int h, int w) {
        m.assign(h, vector<T>(w));
    }
    void assign(int h, int w, const T init) {
        m.assign(h, vector<T>(w, init));
    }
    inline int size() const {
        return m.size();
    }
    void in() {
        for(vector<T> &v : m)
            for(T &val : v) cin >> val;
    }
    void in(int h, int w) {
        m.resize(h, vector<T>(w));
        in();
    }
    void out() {
        int h = m.size();
        for(vector<T> &v : m) {
            int sz = v.size();
            for(int j = 0; j < sz; j++) {
                cout << v[j] << (j == sz - 1 ? '\n' : ' ');
            }
        }
        cout << flush;
    }
    inline vector<T> &operator[](int idx) {
        assert(0 <= idx && idx < int(m.size()));
        return m[idx];
    }
    bool rangeout(int x, int y) {
        if(x < 0 || y < 0 || x >= size() || y >= m[x].size()) return true;
        return false;
    }
};
long long binpow(long long a, long long ex, long long p = MMPRIME) {
    long long res = 1;
    while(ex > 0) {
        if(ex & 1) (res *= a) %= p;
        ex >>= 1;
        (a *= a) %= p;
    }
    return res;
}
inline void init_e(v2d<int> &E, int n, int m, int c) {
    E.assign(n, 0);
    int u, v;
    for(int i = 0; i < m; i++) {
        cin >> u >> v;
        u += c;
        v += c;
        E[u].emplace_back(v);
        E[v].emplace_back(u);
    }
}
// -------------------- main code -------------------- //
template<int mod> struct modint {
private:
    long long val;
public:
    modint(long long x = 0) : val((mod + x % mod) % mod) {}
private:
    modint inv() const {
        long long x_ = val, xd = 1, xdd = 0, y_ = mod, yd = 0, ydd = 1, div;
        while(true) {
            if(!y_) return modint(xd);
            div = x_ / y_;
            x_ -= div * y_;
            xd -= div * yd;
            xdd -= div * ydd;
            if(!x_) return modint(yd);
            div = y_ / x_;
            y_ -= div * x_;
            yd -= div * xd;
            ydd -= div * xdd;
        }
    }
public:
    modint operator-() const {
        return modint(-val);
    }
    modint &operator+=(const modint &a) {
        val += a.val;
        if(val >= mod) val -= mod;
        return *this;
    }
    modint &operator-=(const modint &a) {
        val -= a.val;
        if(val < 0) val += mod;
        return *this;
    }
    modint &operator*=(const modint &a) {
        (val *= a.val) %= mod;
        return *this;
    }
    modint &operator/=(const modint &a) {
        return (*this) *= a.inv();
    }
    modint &operator+=(const long long &a) {
        (val += mod + a % mod) %= mod;
        return *this;
    }
    modint &operator-=(const long long &a) {
        (val += mod - a % mod) %= mod;
        return *this;
    }
    modint &operator*=(const long long &a) {
        (val *= mod + a % mod) %= mod;
        return *this;
    }
    modint &operator/=(const long long &a) {
        return (*this) /= modint(a);
    }
    modint operator+(const modint &a) const {
        return modint(*this) += a;
    }
    modint operator-(const modint &a) const {
        return modint(*this) -= a;
    }
    modint operator*(const modint &a) const {
        return modint(*this) *= a;
    }
    modint operator/(const modint &a) const {
        return modint(*this) /= a;
    }
    modint operator+(const long long &a) const {
        return modint(*this) += a;
    }
    modint operator-(const long long &a) const {
        return modint(*this) -= a;
    }
    modint operator*(const long long &a) const {
        return modint(*this) *= a;
    }
    modint operator/(const long long &a) const {
        return modint(*this) /= modint(a);
    }
    modint &operator++() {
        (++val) %= mod;
        return *this;
    }
    modint operator++(int) {
        modint res(*this);
        (++val) %= mod;
        return res;
    }
    modint &operator--() {
        (val += mod - 1) %= mod;
        return *this;
    }
    modint operator--(int) {
        modint res(*this);
        (val += mod - 1) %= mod;
        return res;
    }
    bool operator==(const modint &a) const {
        return val == a.val;
    }
    bool operator!=(const modint &a) const {
        return val != a.val;
    }
    bool operator<(const modint &a) const {
        return val < a.val;
    }
    bool operator>(const modint &a) const {
        return val > a.val;
    }
    bool operator<=(const modint &a) const {
        return val <= a.val;
    }
    bool operator>=(const modint &a) const {
        return val >= a.val;
    }
    bool operator==(const long long &a) const {
        return val == a;
    }
    bool operator!=(const long long &a) const {
        return val != a;
    }
    bool operator<(const long long &a) const {
        return val < a;
    }
    bool operator>(const long long &a) const {
        return val > a;
    }
    bool operator<=(const long long &a) const {
        return val <= a;
    }
    bool operator>=(const long long &a) const {
        return val >= a;
    }
    modint &operator=(const modint &a) {
        val = a.val;
        return *this;
    }
    modint &operator=(const long long &a) {
        val = (mod + a % mod) % mod;
        return *this;
    }
    friend ostream &operator<<(ostream &os, const modint &a) {
        return os << a.val;
    }
    friend istream &operator>>(istream &is, modint &a) {
        long long n;
        is >> n;
        a = modint(n);
        return is;
    }
};
using mint = modint<998244353>;
template<class T = int> struct UnionFind {
private:
    vector<int> parent;
    vector<int> num;
    vector<T> val;
    int treenum;
    const function<bool(int, int, T &, T &)> swap_flg =
        [this](const int l, const int r, const T &, const T &) { return num[l] < num[r]; };
    const function<void(T &, T &)> merge_val = [this](T &, const T &) {};
public:
    UnionFind(int n) : parent(n), num(n, 1), treenum(n) {
        for(int i = 0; i < n; i++) parent[i] = i;
    }
    UnionFind(int n, function<bool(int, int, T &, T &)> f1) :
        parent(n), num(n, 1), val(n), treenum(n), swap_flg(f1) {
        for(int i = 0; i < n; i++) parent[i] = i;
    }
    UnionFind(int n, const function<void(T &, T &)> f2) :
        parent(n), num(n, 1), val(n), treenum(n), merge_val(f2) {
        for(int i = 0; i < n; i++) parent[i] = i;
    }
    UnionFind(int n, function<bool(int, int, T &, T &)> f1, const function<void(T &, T &)> f2) :
        parent(n), num(n, 1), val(n), treenum(n), swap_flg(f1), merge_val(f2) {
        for(int i = 0; i < n; i++) parent[i] = i;
    }
    UnionFind(vector<T> &v, const function<void(T &, T &)> f2) :
        parent(v.size()), num(v.size(), 1), val(v), treenum(v.size()), merge_val(f2) {
        for(int i = 0; i < v.size(); i++) parent[i] = i;
    }
    UnionFind(vector<T> &v, function<bool(int, int, T &, T &)> f1, const function<void(T &, T &)> f2) :
        parent(v.size()), num(v.size(), 1), val(v), treenum(v.size()), swap_flg(f1), merge_val(f2) {
        for(int i = 0; i < v.size(); i++) parent[i] = i;
    }
    int root(int x) {
        assert(x < parent.size());
        if(parent[x] == x) return x;
        return parent[x] = root(parent[x]);
    }
    int size(int x) {
        assert(x < parent.size());
        return num[root(x)];
    }
    int merge(int x, int y) {
        assert(x < parent.size() && y < parent.size());
        int xrt = root(x);
        int yrt = root(y);
        if(xrt == yrt) return xrt;
        if(swap_flg(xrt, yrt, val[xrt], val[yrt])) swap(xrt, yrt);
        parent[yrt] = xrt;
        num[xrt] += num[yrt];
        merge_val(val[xrt], val[yrt]);
        treenum--;
        return xrt;
    }
    bool same(int x, int y) {
        assert(x < parent.size() && y < parent.size());
        return root(x) == root(y);
    }
    int tnum() {
        return treenum;
    }
    inline T &operator[](int x) {
        assert(x < parent.size());
        return val[x];
    }
};
int N, M;
vector<mint> A;
void input() {
    cin >> N >> M;
    init(A, N);
}
void solve() {
    auto mrg = [](mint &l, mint &r) { l += r; };
    auto uf = UnionFind<mint>(A, mrg);
    for(int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        uf.merge(u, v);
    }
    mint ans = 1;
    for(int i = 0; i < N; i++) {
        if(uf.root(i) == i) {
            rep(j, uf.size(i)) ans *= uf[i];
        }
    }
    out(ans);
}
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    int t = 1;
    // cin >> t;
    while(t--) {
        input();
        solve();
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0