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

提出ソース

結果

問題	No.2563 色ごとのグループ
ユーザー	naimonon77
提出日時	2024-01-10 01:57:07
言語	C++17(clang) (17.0.6 + boost 1.83.0)
結果	RE
実行時間	-
コード長	5,250 bytes
コンパイル時間	2,387 ms
コンパイル使用メモリ	165,632 KB
実行使用メモリ	11,392 KB
最終ジャッジ日時	2024-09-27 20:08:18
合計ジャッジ時間	7,104 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	3 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	3 ms 6,944 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	3 ms 6,944 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	3 ms 6,944 KB
testcase_15	AC	3 ms 6,944 KB
testcase_16	AC	3 ms 6,944 KB
testcase_17	AC	3 ms 6,944 KB
testcase_18	AC	3 ms 6,944 KB
testcase_19	AC	4 ms 6,940 KB
testcase_20	AC	9 ms 6,944 KB
testcase_21	AC	6 ms 6,940 KB
testcase_22	AC	5 ms 6,940 KB
testcase_23	AC	7 ms 6,940 KB
testcase_24	AC	56 ms 6,940 KB
testcase_25	AC	53 ms 7,424 KB
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	RE	-
testcase_31	RE	-
testcase_32	RE	-
testcase_33	RE	-
testcase_34	RE	-
testcase_35	RE	-
testcase_36	RE	-
testcase_37	RE	-

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

ソースコード

raw source code

#define NOMINMAX
#define TEST_MODE true

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
#include <regex>

using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rep2(i,a,b) for(int i=(a);i<(int)(b);++i)
#define rrep(i,n) for(int i=(n)-1;i>=0;--i)
#define rrep2(i,a,b) for(int i=(a)-1;i>=(int)b;--i)
#define range(i,a,b,c) for(int i=a;c>0?i<b:i>b;i+=c)

#define chmax(a,b) (a=(a)<(b)?(b):(a))
#define chmin(a,b) (a=(a)>(b)?(b):(a))

//template<typename T>void out(T a) {T b=a;if(a==inf)b=-1;cout<<a<<endl;}
//#define out(a) cout<<(a)<<endl
//#define o2(a,b) cout<<(a)<<" ";out(b)
//#define o3(a,b,c) cout<<(a)<<" ";o2(b, c)
#define abp(o,a,b) out(((o)?a:b))
#define YEP(x) abp(x,"YES","NO")
#define Yep(x) abp(x,"Yes","No")


using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define all(a) begin(a),end(a)
#define ifnot(a) if(!(a))
#define int long long

#ifdef LOCAL_ENV

#if TEST_MODE==true
const bool test = true;
#define dump(x) cerr<<#x<<" : "<<(x)<< "   \t"
#define dumpl(x) dump(x)<<endl
#define cerr_endl cerr<<endl
#else
const bool test = false;
#define dump(x) 
#define dumpl(x)
#define cerr_endl 
#endif

#else
const bool test = false;
#define dump(x) 
#define dumpl(x)
#define cerr_endl 
#endif

int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
const int inf = (int)1 << 60;
const int undefined = inf;
const ll INFL = (ll)1 << 60;
ll mod_n = (int)1e9 + 7;
const double eps = 1e-10;
typedef long double Real;
// return -1, 0, 1
int sgn(const Real& r) { return(r > eps) - (r < -eps); }
int sgn(const Real& a, const Real& b) { return sgn(a - b); }

const int MAX = (int)2e6 + 5;
const int MAX2 = 2005;

vector<string> split(const string& str, char sep) { vector<string> v; stringstream ss(str); string buffer; while (getline(ss, buffer, sep)) v.push_back(buffer); return v; }

string join(const vector<string>& v, const string delim = 0) { string s; if (!v.empty()) { s += v[0]; for (decltype(v.size()) i = 1, c = v.size(); i < c; ++i) { if (delim != "")s += delim; s += v[i]; } }return s; }

string operator*(const string& s, const int& n) { string res = ""; rep(i, n)res += s; return res; }

template<typename T>
int sum_f(T a) { return accumulate(all(a), 0ll); }

template<typename T>T gcd(T a, T b) { T c; while (a != 0) { c = a; a = b % a; b = c; }; return b; }
template<typename T>T bit_count(T N) { T c = 0; while (N) { if (N & 1)c++; N >>= 1; }return c; }


template<typename T>void p_vector(vector<pair<T, T>> a, ostream& o = cout) { rep(i, a.size())o << a[i].first << "," << a[i].second << " "; o << endl; }

template<typename T>void p_vector(vector<T> a, ostream& o = cout) { rep(i, a.size() - 1)o << a[i] << " "; o << a.back() << endl; }

ll pow_n(ll x, ll n) { ll r = 1; while (n > 0) { if (n & 1)r = (r * x) % mod_n; x = (x * x) % mod_n; n >>= 1; }return r; }

int H, W;

#define grid_ng(y,x) (y<0||y>=H||x<0||x>=W)

int div_ceil(int a, int b) { int r = a / b; if (a % b != 0)r++; return r; }

int math_div(int x, int m) {
	ll r = (x % m + m) % m;
	return (x - r) / m;
}

#define i1(a) cin>>a;
#define i2(a,b) cin>>a>>b;
#define i3(a,b,c) cin>>a;i2(b,c);
#define i4(a,b,c,d) cin>>a;i3(b,c,d);
#define i5(a,b,c,d,e) cin>>a;i4(b,c,d,e);


template<typename T>
vector<T> in_vec(int n) {
	vector<T> a(n);
	a.resize(n);
	rep(i, n) cin >> a[i];
	return a;
}

template<typename T>
vector<vector<int>> in_vec(int n, int m) {
	vector<vector<int>> a(n);
	rep(i, n) {
		a[i].resize(m);
		rep(j, m) cin >> a[i][j];
	}
	return a;
}

template<typename First>
void out(First first) {
	cout << first << endl;
}

template<typename First, typename... Rest>
void out(First first, Rest... rest) {
	cout << first << " ";
	out(rest...);
}

template<class T, size_t n, size_t idx = 0>
auto make_vec(const size_t(&d)[n], const T& init) noexcept {
	if constexpr (idx < n) return std::vector(d[idx], make_vec<T, n, idx + 1>(d, init));
	else return init;
}

template<class T, size_t n>
auto make_vec(const size_t(&d)[n]) noexcept {
	return make_vec(d, T{});
}

bool is_bit_on(int b, int i) {
	return (b >> i) & 1;
}

template<typename X, typename Y>
vector<Y> python_map(function<Y(X)>f, vector<X>xs) {
	vector<Y> ys;
	for (X x : xs) {
		auto y = f(x);
		ys.push_back(y);
	}
	p_vector(ys);
	return ys;
};

struct Point {
	int y, x;
};

// end of template

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool same(int x, int y) {
		return root(x) == root(y);
	}
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};


void solve() {
	UnionFind uf(100000);
	int n, m; cin >> n >> m;
	auto c = in_vec<int>(n);
	set<int> color_set;
	rep(i, n) color_set.insert(c[i]);

	rep(i, m) {
		int a, b; cin >> a >> b;
		a--; b--;
		if (c[a] == c[b]) {
			uf.unite(a, b);
		}
	}
	int cnt = 0;
	rep(i, n) {
		if (uf.root(i) == i) cnt++;
	}
	out(cnt - color_set.size());
}













signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cout << fixed << setprecision(20);
	solve();
	return 0;
}

yukicoder

結果

テストケース

ソースコード