結果
問題 | No.2563 色ごとのグループ |
ユーザー |
|
提出日時 | 2023-12-02 15:03:01 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 191 ms / 2,000 ms |
コード長 | 4,626 bytes |
コンパイル時間 | 6,735 ms |
コンパイル使用メモリ | 317,184 KB |
実行使用メモリ | 18,716 KB |
最終ジャッジ日時 | 2024-09-26 17:57:38 |
合計ジャッジ時間 | 9,146 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using ll = long long;using ld = long double;using st = string;using mint = atcoder::modint998244353;using Mint = atcoder::modint1000000007;#define vl vector<ll>#define vvl vector<vector<ll>>#define vd vector<ld>#define vvd vector<vector<ld>>#define vb vector<bool>#define vs vector<string>#define vp vector<pair<ll,ll>>#define vm vector<mint>#define vvm vector<vector<mint>>#define vM vector<Mint>#define vvM vector<vector<Mint>>#define chmax(n,v) n=n<v?v:n#define chmin(n,v) n=n>v?v:n#define all(n) begin(n),end(n)#define rev(n) reverse(all(n))#define sor(n) stable_sort(all(n))#define rep(i,n) for(ll i=0;i<(n);++i)#define rrep(i,a,n) for(ll i=a;i<(n);++i)#define sz(n) n.size()#define bit(n,shift) ((n&(1<<shift))!=0)#define yn(x) cout << (x?"Yes":"No") << endl;#define lb(a,n) lower_bound(a.begin(),a.end(),n)-a.begin()#define ub(a,n) upper_bound(a.begin(),a.end(),n)-a.begin()#define lb2(a,n) *lower_bound(a.begin(),a.end(),n)#define ub2(a,n) *upper_bound(a.begin(),a.end(),n)template <typename T> void input(T &a) { cin >> a; };template <typename T1, typename... T2> void input(T1&a, T2 &...b) { cin >> a; input(b...); };const ll inf = 1e18;//std::setprecision(13); 出力桁を増やす//2^29<10^9ll di[8]={1,-1,0,0,1,1,-1,-1};ll dj[8]={0,0,1,-1,1,-1,-1,1};//ll da[4]={1,1,-1,-1};//ll db[4]={1,-1,-1,1};//ll na[4]={1,0,1,0};//ll nb[4]={0,1,0,1};template<typename T = ll>vector<T> rd(size_t n) {vector<T> ts(n);for (size_t i = 0; i < n; i++) cin >> ts[i];return ts;}bool is_prime(ll N) {if (N == 1) return false;for (ll i = 2; i * i <= N; ++i) {if (N % i == 0) return false;}return true;}int calc_digit(ll N){int res = 0;while(N>0){res++;N/=10;}return res;}ll factorial(ll n, ll mod = 1e18) {ll ans = 1;for(ll i = n; i >= 2; i--) ans = (ans * i) % mod;return ans;}void printl(vl v){ll vsz=v.size();for(ll i=0;i<vsz;i++){cout << v[i] << endl;}}void prints(vs v){ll vsz=v.size();for(ll i=0;i<vsz;i++){cout << v[i] << endl;}}ll round_up(ll x,ll y){return (x+y-1)/y;}bool in_out(ll x,ll y,ll h,ll w){return 0<=x and x<h and 0<=y and y<w;}struct UnionFind{vector<ll> par;vector<ll> size;UnionFind(ll n){par.resize(2*(n+1),-1);size.resize(2*(n+1),1);}ll root(ll x){if (par[x]==-1) return x;return par[x]=root(par[x]);}void unite(ll u,ll v){ll uu=root(u),vv=root(v);if(uu==vv){return;}if(size[uu]<size[vv]){par[uu]=vv;size[vv]+=size[uu];}else{par[vv]=uu;size[uu]+=size[vv];}return;}bool same(ll u,ll v){return root(u)==root(v);}};const int MAX = 510000;mint fac[MAX], finv[MAX], inv[MAX];// テーブルを作る前処理void COMinit() {const int MOD = mint::mod();fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i;inv[i] = MOD - inv[MOD%i] * (MOD / i);finv[i] = finv[i - 1] * inv[i];}}// 二項係数計算mint COM(int n, int k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * finv[k] * finv[n - k];}vector<pair<ll, ll>> prime_factorize(ll N){vector<pair<ll, ll> > res;for (ll a = 2; a * a <= N; ++a) {if (N % a != 0) continue;ll ex = 0;while (N % a == 0) {ex++;N /= a;}res.push_back({a, ex});}if (N != 1) res.push_back({N, 1});return res;}vl p_list(ll n){vl res;vb check(n+1);for(ll i=2;i<=n;i++){if(check[i]) continue;res.push_back(i);ll ii=i;while(ii<=n){check[ii]=true;ii+=i;}}return res;}vl cumulative_sum(vl a){ll s=sz(a);vl b(s+1,0);for(ll i=0;i<s;i++){b[i+1]=a[i]+b[i];}return b;}int main(){ll n,m;cin >> n >> m;vl c(n);rep(i,n){cin >> c[i];c[i]--;}UnionFind t(n);rep(i,m){ll u,v;cin >> u >> v;u--,v--;if(c[u]==c[v]) t.unite(u,v);}vl cnt(n,0);rep(i,n){if(t.root(i)==i) cnt[c[i]]++;}ll ans=0;rep(i,n){if(cnt[i]) ans+=(cnt[i]-1);}cout << ans;}