結果
問題 | No.2563 色ごとのグループ |
ユーザー |
![]() |
提出日時 | 2023-09-28 00:19:36 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 412 ms / 2,000 ms |
コード長 | 2,859 bytes |
コンパイル時間 | 2,050 ms |
コンパイル使用メモリ | 182,428 KB |
実行使用メモリ | 22,912 KB |
最終ジャッジ日時 | 2024-09-26 16:32:02 |
合計ジャッジ時間 | 7,758 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:108:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 108 | for(auto&& [k,l]:mp) ans+=l-1; | ^
ソースコード
#include<bits/stdc++.h> /// @brief Union-Find 木 /// @note 1.4 高速化 + 省メモリ化 /// @see https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-find class UnionFind { public: UnionFind() = default; /// @brief Union-Find 木を構築します。 /// @param n 要素数 explicit UnionFind(size_t n) : m_parentsOrSize(n, -1) {} /// @brief 頂点 i の root のインデックスを返します。 /// @param i 調べる頂点のインデックス /// @return 頂点 i の root のインデックス int find(int i) { if (m_parentsOrSize[i] < 0) { return i; } // 経路圧縮 return (m_parentsOrSize[i] = find(m_parentsOrSize[i])); } /// @brief a のグループと b のグループを統合します。 /// @param a 一方のインデックス /// @param b 他方のインデックス void merge(int a, int b) { a = find(a); b = find(b); if (a != b) { // union by size (小さいほうが子になる) if (-m_parentsOrSize[a] < -m_parentsOrSize[b]) { std::swap(a, b); } m_parentsOrSize[a] += m_parentsOrSize[b]; m_parentsOrSize[b] = a; } } /// @brief a と b が同じグループに属すかを返します。 /// @param a 一方のインデックス /// @param b 他方のインデックス /// @return a と b が同じグループに属す場合 true, それ以外の場合は false bool connected(int a, int b) { return (find(a) == find(b)); } /// @brief i が属するグループの要素数を返します。 /// @param i インデックス /// @return i が属するグループの要素数 int size(int i) { return -m_parentsOrSize[find(i)]; } private: // m_parentsOrSize[i] は i の 親, // ただし root の場合は (-1 * そのグループに属する要素数) std::vector<int> m_parentsOrSize; }; using namespace std; typedef long long ll; #define rep(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rrep(i,a,b) for(ll i=(ll)(a-1);i>=(ll)(b);i--) #define MOD 998244353 //#define MOD 1000000007 #define INF 1e18 #define Pair pair<ll,ll> //#define PI numbers::pi //#define E numbers::e template <typename T> bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;} template <typename T> bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;} ll dx[8]={-2,-1,1,2,-2,-1,1,2}; ll dy[8]={-1,-2,-2,-1,1,2,2,1}; int main(){ ll n,m; cin >> n >> m; vector<ll> c(n); rep(i,0,n) cin >> c[i]; UnionFind uf(n); rep(i,0,m){ ll u,v; cin >> u >> v; u--,v--; if(c[u]==c[v]) uf.merge(u,v); } map<ll,ll> mp; set<ll> st; rep(i,0,n){ if(st.count(uf.find(i))) continue; mp[c[i]]++; st.insert(uf.find(i)); } ll ans=0; for(auto&& [k,l]:mp) ans+=l-1; cout << ans << endl; //for(auto&& [k,l]:mp) cout << k << ' ' << l << endl; }