結果
| 問題 | No.2563 色ごとのグループ |
| ユーザー |
 shogo314
|
| 提出日時 | 2023-12-02 15:53:30 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 161 ms / 2,000 ms |
| コード長 | 8,670 bytes |
| コンパイル時間 | 3,142 ms |
| コンパイル使用メモリ | 259,136 KB |
| 実行使用メモリ | 13,440 KB |
| 最終ジャッジ日時 | 2024-09-26 19:27:52 |
| 合計ジャッジ時間 | 6,199 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
#line 2 "/home/shogo314/cpp_include/ou-library/io.hpp"/*** @file io.hpp* @brief 空白区切り出力、iostreamのオーバーロード*/#include <array>#include <iostream>#include <utility>#include <tuple>#include <vector>namespace tuple_io {template <typename Tuple, size_t I, typename CharT, typename Traits>std::basic_istream<CharT, Traits>& read_tuple(std::basic_istream<CharT, Traits>& is, Tuple& t) {is >> std::get<I>(t);if constexpr (I + 1 < std::tuple_size_v<Tuple>) {return read_tuple<Tuple, I + 1>(is, t);}return is;}template <typename Tuple, size_t I, typename CharT, typename Traits>std::basic_ostream<CharT, Traits>& write_tuple(std::basic_ostream<CharT, Traits>& os, const Tuple& t) {os << std::get<I>(t);if constexpr (I + 1 < std::tuple_size_v<Tuple>) {os << CharT(' ');return write_tuple<Tuple, I + 1>(os, t);}return os;}};template <typename T1, typename T2, typename CharT, typename Traits>std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::pair<T1, T2>& p) {is >> p.first >> p.second;return is;}template <typename... Types, typename CharT, typename Traits>std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::tuple<Types...>& p) {return tuple_io::read_tuple<std::tuple<Types...>, 0>(is, p);}template <typename T, size_t N, typename CharT, typename Traits>std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::array<T, N>& a) {for(auto& e : a) is >> e;return is;}template <typename T, typename CharT, typename Traits>std::basic_istream<CharT, Traits>& operator>>(std::basic_istream<CharT, Traits>& is, std::vector<T>& v) {for(auto& e : v) is >> e;return is;}template <typename T1, typename T2, typename CharT, typename Traits>std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::pair<T1, T2>& p) {os << p.first << CharT(' ') << p.second;return os;}template <typename... Types, typename CharT, typename Traits>std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::tuple<Types...>& p) {return tuple_io::write_tuple<std::tuple<Types...>, 0>(os, p);}template <typename T, size_t N, typename CharT, typename Traits>std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::array<T, N>& a) {for(size_t i = 0; i < N; ++i) {if(i) os << CharT(' ');os << a[i];}return os;}template <typename T, typename CharT, typename Traits>std::basic_ostream<CharT, Traits>& operator<<(std::basic_ostream<CharT, Traits>& os, const std::vector<T>& v) {for(size_t i = 0; i < v.size(); ++i) {if(i) os << CharT(' ');os << v[i];}return os;}/*** @brief 空行出力*/void print() { std::cout << '\n'; }/*** @brief 出力して改行** @tparam T 型* @param x 出力する値*/template <typename T>void print(const T& x) { std::cout << x << '\n'; }/*** @brief 空白区切りで出力して改行** @tparam T 1つ目の要素の型* @tparam Tail 2つ目以降の要素の型* @param x 1つ目の要素* @param tail 2つ目以降の要素*/template <typename T, typename... Tail>void print(const T& x, const Tail&... tail) {std::cout << x << ' ';print(tail...);}#line 2 "/home/shogo314/cpp_include/ou-library/unionfind.hpp"/*** @file unionfind.hpp* @brief UnionFind*/#include <algorithm>#include <cassert>#line 11 "/home/shogo314/cpp_include/ou-library/unionfind.hpp"/*** @brief 無向グラフに対して「辺の追加」、「2頂点が連結かの判定」をする*/struct UnionFind {private:int _n;// 負ならサイズ、非負なら親std::vector<int> parent_or_size;public:UnionFind() : _n(0) {}explicit UnionFind(int n) : _n(n), parent_or_size(n, -1) {}/*** @brief 辺(a,b)を足す* @return 連結したものの代表元*/int merge(int a, int b) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);int x = leader(a), y = leader(b);if (x == y) return x;if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);parent_or_size[x] += parent_or_size[y];parent_or_size[y] = x;return x;}/*** @brief 頂点a,bが連結かどうか*/bool same(int a, int b) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);return leader(a) == leader(b);}/*** @brief 頂点aの属する連結成分の代表元*/int leader(int a) {assert(0 <= a && a < _n);if (parent_or_size[a] < 0) return a;int x = a;while (parent_or_size[x] >= 0) {x = parent_or_size[x];}while (parent_or_size[a] >= 0) {int t = parent_or_size[a];parent_or_size[a] = x;a = t;}return x;}/*** @brief 頂点aの属する連結成分のサイズ*/int size(int a) {assert(0 <= a && a < _n);return -parent_or_size[leader(a)];}/*** @brief グラフを連結成分に分け、その情報を返す* @return 「一つの連結成分の頂点番号のリスト」のリスト*/std::vector<std::vector<int>> groups() {std::vector<int> leader_buf(_n), group_size(_n);for (int i = 0; i < _n; i++) {leader_buf[i] = leader(i);group_size[leader_buf[i]]++;}std::vector<std::vector<int>> result(_n);for (int i = 0; i < _n; i++) {result[i].reserve(group_size[i]);}for (int i = 0; i < _n; i++) {result[leader_buf[i]].push_back(i);}result.erase(std::remove_if(result.begin(), result.end(),[&](const std::vector<int>& v) { return v.empty(); }),result.end());return result;}};#line 1 "/home/shogo314/cpp_include/sh-library/base.hpp"#include <bits/stdc++.h>#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")using namespace std;using ll = long long;using str = string;using pl = pair<ll, ll>;template <typename T>using ml = map<ll, T>;using mll = map<ll, ll>;using sl = set<ll>;using ld = long double;using pd = pair<ld, ld>;template <typename T>using vec = vector<T>;template <typename T>using vv = vector<vector<T>>;template <typename T>using vvv = vector<vector<vector<T>>>;template <typename T1, typename T2>using vp = vector<pair<T1, T2>>;using vl = vec<ll>;using vvl = vv<ll>;using vs = vec<str>;using vc = vec<char>;using vpl = vec<pl>;using spl = set<pl>;using vd = vec<ld>;using vpd = vec<pd>;template <typename T, int N>using ary = array<T, N>;template <int N>using al = array<ll, N>;template <int N1, int N2>using aal = array<array<ll, N2>, N1>;template <int N>using val = vec<al<N>>;#define all(obj) (obj).begin(), (obj).end()#define reps(i, a, n) for (ll i = (a); i < ll(n); i++)#define rep(i, n) reps(i, 0, (n))#define rrep(i, n) reps(i, 1, (n) + 1)#define repds(i, a, n) for (ll i = ((n) - 1); i >= (a); i--)#define repd(i, n) repds(i, 0, (n))#define rrepd(i, n) repds(i, 1, (n) + 1)#define rep2(i, j, x, y) rep(i, x) rep(j, y)template <typename T1, typename T2>inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b;return true;}return false;}template <typename T1, typename T2>inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b;return true;}return false;}#define LL(x) ll x;cin >> x;#define VL(a,n) vl a(n);cin >> a;#define VS(a,n) vs a(n);cin >> a;#define STR(s) str s;cin >> s;#define VPL(a,n) vpl a(n);cin >> a;#define VAL(a,n,k) val<k> a(n);cin >> a;#line 4 "main.cpp"void solve() {LL(N);LL(M);VL(C, N);UnionFind uf(N);rep(i, M) {LL(u);LL(v);u--;v--;if (C[u] == C[v])uf.merge(u, v);}mll m;ll ans = 0;rep(i, N) {if (m.find(C[i]) == m.end()) {m[C[i]] = i;} else {if (not uf.same(m[C[i]], i)) {uf.merge(m[C[i]], i);ans++;}}}print(ans);}int main() {cin.tie(nullptr);ios_base::sync_with_stdio(false);solve();}