結果

問題 No.2563 色ごとのグループ
ユーザー ueta
提出日時 2023-12-02 15:00:51
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 108 ms / 2,000 ms
コード長 9,160 bytes
コンパイル時間 2,948 ms
コンパイル使用メモリ 165,632 KB
実行使用メモリ 21,760 KB
最終ジャッジ日時 2024-09-26 17:53:43
合計ジャッジ時間 5,931 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
#include <cstdint>
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define fore(i, a) for(auto &&i : a)
#define foreP(a, b, v) for(auto &&[a, b] : v)
#define foreP3(a, b, c, v) for(auto &&[a, b, c] : v)
#define fitr(itr, m) for(auto &&itr=m.begin();itr!=m.end();itr++)
#define ALL(v) (v).begin(),(v).end()
#define SUM(a) accumulate(ALL(a),0LL)
#define VC vector
#define TP tuple
using namespace std;
mt19937 engine(time(0));
using ll = long long;
using ld = long double;
constexpr long long mod = 998244353;
// constexpr long long mod = 1000000007;
// constexpr long long mod = 100000000000000003;
constexpr double PI=3.1415926535897932384626433832795028841971;
constexpr long long inf = INT_MAX;
constexpr long long infll = LONG_MAX;
int dx[8] = {1, 0,-1, 0, 1, 1,-1,-1};
int dy[8] = {0, 1, 0,-1, 1,-1, 1,-1 };
using Si =set<int>;using Sll =set<long long>;using Sc =set<char>;using Ss =set<string>;
using Mii = map<int,int>;using Msi = map<string,int>;using Mci = map<char,int>;using Mlli = map<long long,int>;
using P = pair<int, int>;using PL = pair<long long, long long>;
using V = vector<int>;using VL = vector<long long>;using Vc = vector<char>;using Vs = vector<string>;
using VP = vector<P>;using VPL = vector<P>;
using VV = vector<vector<int>>;using VVL = vector<vector<long long>>;
using VVc = vector<vector<char>>;using VVs = vector<vector<string>>;
using VVP = vector<vector<P>>;using VVPL = vector<vector<PL>>;
using VVV = vector<vector<vector<int>>>;using VVVL = vector<vector<vector<ll>>>;using VVVP = vector<vector<vector<P>>>;
template<class T,class S>bool chmin(T& a, S b) {if(a<=b)return false;a = b;return true;};
template<class T,class S>bool chmax(T& a, S b) {if(a>=b)return false;a = b;return true;};
ll modpow(ll x, ll n, ll m = mod) {
    if (n < 0) {ll res = modpow(x, -n, m);return modpow(res, m - 2, m);}
    if (abs(x) >= m)x %= m;if (x < 0)x += m;//if (x == 0)return 0;
    ll res = 1;
    while (n) {if (n & 1)res = res * x % m;x = x * x % m; n >>= 1;}
    return res;
}
class modint {
public:
    int val;
    modint() :val(0) {}
    template<typename T>modint(T x=0): val(x%mod){if(val<0)val+=mod;}
    modint(const modint &r){val=r.val;}
    modint& operator=(const modint& other) {val = other.val;return *this;}
    modint& operator=(const int& other) {val = other;return *this;}
    modint& operator=(const long long& other) {val = other;return *this;}
    //算術演算子
    modint operator +(){return (*this);} //単項
    modint operator -(){return (val%mod+mod)%mod;} //単項
    modint operator +(const modint &r){return modint(*this)+=r;}
    modint operator -(const modint &r){return modint(*this)-=r;}
    modint operator *(const modint &r){return modint(*this)*=r;}
    modint operator /(const modint &r){return modint(*this)/=r;}
    modint operator %(const modint &r){return modint(*this)%=r;}
    modint operator ^(long long r){modint ans = 1, x = val;while (r > 0) {if (r & 1) ans *= x;x *= x;r >>= 1;}return ans;}
    modint operator ++(int){val+=1;val%=mod; return *this;}
    modint operator --(int){(val==0)?val=mod-1:val-=1; return *this;}
    //代入演算子
    modint &operator +=(const modint &r){val+=r.val;if(val>=mod)val-=mod;return *this;}
    modint &operator -=(const modint &r){if(val<r.val)val+=mod;val-=r.val;return *this;}
    modint &operator *=(const modint &r){val=(ll)val*r.val%mod;return *this;}
    modint &operator /=(const modint &r){ll a=r.val,b=mod,u=1,v=0;while(b){ll t=a/b;a-=t*b;swap(a,b);u-=t*v;swap(u,v);}val=val*u%mod;if(val<0)val
        +=mod;return *this;}
    modint &operator %=(const modint &r){val=val%r.val; return *this;}
    modint &operator ^=(const long long &r){(*this)=(*this)^r; return (*this);}
    //等価比較演算子
    bool operator ==(const modint& r){return this->val==r.val;}
    bool operator <(const modint& r){return this->val<r.val;}
    bool operator >(const modint& r){return this->val>r.val;}
    bool operator !=(const modint& r){return this->val!=r.val;}
    // 他のクラスとの計算
    template <typename T>friend modint operator+(T t, const modint& o) {return modint(t) + o;}
    template <typename T>friend modint operator-(T t, const modint& o) {return modint(t) - o;}
    template <typename T>friend modint operator*(T t, const modint& o) {return modint(t) * o;}
    template <typename T>friend modint operator/(T t, const modint& o) {return modint(t) / o;}
};
istream &operator >>(istream &is,modint& x){ long long t; is >> t; x=modint(t); return is;}
ostream &operator <<(ostream &os,const modint& x){return os<<x.val;}
const int max_n = 1 << 20;
modint fact[max_n], factinv[max_n];
void init_f() {
    fact[0] = (1);
    for (int i = 0; i < max_n - 1; i++) {
        fact[i + 1] = fact[i] * (i + 1);
    }
    factinv[max_n - 1] = (1) / fact[max_n - 1];
    for (int i = max_n - 2; i >= 0; i--) {
        factinv[i] = factinv[i + 1] *(i + 1);
    }
}
modint comb(int a, int b) {
    if (a < 0 || b < 0 || a < b)return 0;
    return fact[a] * factinv[b] * factinv[a - b];
}
modint combP(int a, int b) {
    if (a < 0 || b < 0 || a < b)return 0;
    return fact[a] * factinv[a - b];
}
template<typename T>
T gcd(T a, T b) {
    a = abs(a); b = abs(b);
    if (a < b)swap(a, b);
    while(b){ll r = a % b; a = b; b = r;}
    return a;
}
template <class T,class S> istream &operator>>(istream &is, pair<T,S> &pir) {is >> pir.first >> pir.second; return is;}
template <class T> istream &operator>>(istream &is, vector<T> &vec) {for(T &i: vec) is >> i; return is;}
template <class... T> istream &operator>>(istream &is, tuple<T...> &tpl) {apply([&is](auto &&...args) { ((is >> args), ...); }, tpl);return is;}
template <class OStream, class T> OStream &operator<<(OStream &os, const vector<T> &vec) {auto itr = vec.begin();while (itr != vec.end()){os << *itr; 
    itr++;if(itr!=vec.end())os <<" ";}return os;}
template <class OStream, class T, size_t sz> OStream &operator<<(OStream &os, const array<T, sz> &arr) {auto itr = arr.begin();while (itr != arr.end
    ()){os << *itr; itr++;if(itr!=arr.end())os <<" ";}return os;}
template <class OStream, class... T> OStream &operator<<(OStream &os, const tuple<T...> &tpl) {apply([&os](auto &&...args) {int count = 0;((os << 
    args << (++count != sizeof...(args) ? " " : "")), ...);}, tpl);return os;}
template <class OStream, class T, class U> OStream &operator<<(OStream &os, const pair<T, U> &pa) {return os  << pa.first << ' ' << pa.second;}
template <class OStream, class T> OStream &operator<<(OStream &os, const set<T> &vec) {auto itr = vec.begin();while (itr != vec.end()){os << *itr; 
    itr++;if(itr!=vec.end())os <<" ";}return os;}
template <class OStream, class T> OStream &operator<<(OStream &os, const deque<T> &vec) {os << "deq[";for (auto v : vec) os << v << ',';os << ']'
    ;return os;}
template <class OStream, class T> OStream &operator<<(OStream &os, const queue<T> &vec) {os << "que[";for (auto v : vec) os << v << ',';os << ']'
    ;return os;}
template <class OStream, class TK, class TV> OStream &operator<<(OStream &os, const map<TK, TV> &mp) {os << '{';for (auto v : mp) os << v.first << "
    =>" << v.second << ','<< endl;os << '}';return os;}
template<typename T>void out(T a){ cout << a << endl;}
template<typename T,typename S>void out(T a,S b){ cout << a <<" " << b << endl;}
template<typename T,typename S,typename U>void out(T a,S b,U c){ cout << a <<" " << b <<" " << c << endl;}
void yes(bool f=1,string yes="Yes",string no="No"){if(f){cout << yes << endl;}else{cout << no << endl;}}
struct UnionFind
{
    vector<int> tree;
    int n;
    UnionFind(int n) : tree(n, -1),n(n) {}
    int find(int x)
    {
        if (tree[x] < 0)
            return x;
        else
            tree[x] = find(tree[x]);
        return tree[x];
    }
    void unite(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x == y)
            return;
        if (tree[x] > tree[y])
        {
            swap(x, y);
        }
        tree[x] += tree[y];
        tree[y] = x;
        return;
    }
    bool same(int x,int y)
    {
        return find(x)==find(y);
    }
    int size(int x)
    {
        return -tree[find(x)];
    }
    map<int,vector<int>> all_group_members(){
        map<int,vector<int>> group_members{};
        for(int member=0;member<n;member++){
            group_members[find(member)].push_back(member);
        }
        return group_members;
    }
        
};
void solve(){
    int N,M;
    cin >> N >> M;
    V C(N);
    cin >> C;
    UnionFind uf(N);
    while(M--){
        int a, b;
        cin >> a >> b;
        a--, b--;
        if(C[a]==C[b])
            uf.unite(a, b);
    }
    VV c(N+1);
    rep(i,N){
        c[C[i]].push_back(i);
    }
    // rep(i, N + 1) cerr << c[i] << endl;
    int ans = 0;
    rep(i,N+1){
        Rep(j,1,c[i].size()){
            if(!uf.same(c[i][0],c[i][j])){
                ans++;
                uf.unite(c[i][0], c[i][j]);
            }
        }
    }
    out(ans);
    return;
}
int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<setprecision(20);
    int t=1;
    // cin >> t;
    while(t--)
        solve();
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0