#934200 (C++17(clang)) No.2563 色ごとのグループ

提出ソース

結果

問題	No.2563 色ごとのグループ
ユーザー	ueta
提出日時	2023-12-02 15:00:51
言語	C++17(clang) (17.0.6 + boost 1.83.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8 ms 11,520 KB
testcase_01	AC	9 ms 11,520 KB
testcase_02	AC	8 ms 11,648 KB
testcase_03	AC	9 ms 11,648 KB
testcase_04	AC	8 ms 11,520 KB
testcase_05	AC	8 ms 11,648 KB
testcase_06	AC	8 ms 11,648 KB
testcase_07	AC	8 ms 11,648 KB
testcase_08	AC	9 ms 11,648 KB
testcase_09	AC	9 ms 11,648 KB
testcase_10	AC	8 ms 11,648 KB
testcase_11	AC	8 ms 11,648 KB
testcase_12	AC	8 ms 11,520 KB
testcase_13	AC	8 ms 11,520 KB
testcase_14	AC	8 ms 11,776 KB
testcase_15	AC	9 ms 11,776 KB
testcase_16	AC	9 ms 11,776 KB
testcase_17	AC	8 ms 11,776 KB
testcase_18	AC	8 ms 11,776 KB
testcase_19	AC	10 ms 11,776 KB
testcase_20	AC	14 ms 12,288 KB
testcase_21	AC	12 ms 11,904 KB
testcase_22	AC	10 ms 11,904 KB
testcase_23	AC	12 ms 12,032 KB
testcase_24	AC	51 ms 15,360 KB
testcase_25	AC	49 ms 16,000 KB
testcase_26	AC	68 ms 18,432 KB
testcase_27	AC	76 ms 21,248 KB
testcase_28	AC	75 ms 19,072 KB
testcase_29	AC	107 ms 21,760 KB
testcase_30	AC	108 ms 21,632 KB
testcase_31	AC	106 ms 21,632 KB
testcase_32	AC	104 ms 21,632 KB
testcase_33	AC	89 ms 18,776 KB
testcase_34	AC	88 ms 19,032 KB
testcase_35	AC	86 ms 18,776 KB
testcase_36	AC	89 ms 18,776 KB
testcase_37	AC	89 ms 18,904 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード