結果
問題 | No.2563 色ごとのグループ |
ユーザー |
![]() |
提出日時 | 2023-12-02 15:11:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 544 ms / 2,000 ms |
コード長 | 850 bytes |
コンパイル時間 | 2,349 ms |
コンパイル使用メモリ | 211,460 KB |
最終ジャッジ日時 | 2025-02-18 04:20:14 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "settings/debug.cpp" #define _GLIBCXX_DEBUG #else #define Debug(...) void(0) #endif using ll = long long; #define rep(i, n) for (int i = 0; i < (n); ++i) #include<atcoder/dsu> int main() { int n,m;cin>>n>>m; vector<int> c(n); rep(i,n)cin>>c[i]; map<int, set<int>> leads; rep(i, n) leads[c[i]].insert(i); atcoder::dsu d(n); rep(_, m) { int a, b; cin >> a >> b; --a, --b; if (c[a] == c[b]) { int la = d.leader(a); int lb = d.leader(b); if (la != lb) { d.merge(a, b); int nl = d.leader(a); leads[c[a]].erase(la); leads[c[b]].erase(lb); leads[c[nl]].insert(nl); } } } int ans = 0; for (auto [_, s] : leads) { ans += s.size() - 1; } cout << ans << endl; return 0; }