#582039 (C++17) No.1293 2種類の道路

• 問題: No.1293 2種類の道路
• ユーザー: Nachia
• 提出日時: 2020-11-20 22:42:03
• 言語: C++17 (gcc 11.2.0 + boost 1.78.0)
• 結果: AC
• 実行時間: 111 ms / 2,000 ms
• コード長: 865 bytes
• コンパイル時間: 1,907 ms
• 使用メモリ: 9,520 KB
• 最終ジャッジ日時: 2023-02-23 19:11:00
• 合計ジャッジ時間: 4,651 ms
• ジャッジサーバーID （参考情報）: judge13 / judge15

入力	結果	実行時間; 使用メモリ
testcase_00	AC	1 ms; 8,236 KB
testcase_01	AC	2 ms; 8,372 KB
testcase_02	AC	2 ms; 8,296 KB
testcase_03	AC	1 ms; 7,668 KB
testcase_04	AC	1 ms; 7,672 KB
testcase_05	AC	1 ms; 7,592 KB
testcase_06	AC	2 ms; 7,572 KB
testcase_07	AC	1 ms; 7,608 KB
testcase_08	AC	1 ms; 8,296 KB
testcase_09	AC	107 ms; 7,660 KB
testcase_10	AC	110 ms; 7,660 KB
testcase_11	AC	110 ms; 7,660 KB
testcase_12	AC	111 ms; 8,300 KB
testcase_13	AC	106 ms; 7,648 KB
testcase_14	AC	67 ms; 9,520 KB
testcase_15	AC	67 ms; 9,376 KB
testcase_16	AC	91 ms; 7,652 KB
testcase_17	AC	102 ms; 8,296 KB
testcase_18	AC	69 ms; 8,596 KB
testcase_19	AC	73 ms; 9,476 KB
testcase_20	AC	75 ms; 9,520 KB
testcase_21	AC	65 ms; 8,372 KB
testcase_22	AC	66 ms; 8,228 KB
testcase_23	AC	69 ms; 8,312 KB

ソースコード

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using ULL=unsigned long long;
#define rep(i,n) for(int i=0;i<(n);i++)

struct dsu{
  vector<int> V;
  vector<int> Z;
  dsu(int n){ V.resize(n); rep(i,n) V[i]=i; Z.assign(n,1); }
  int root(int a){ if(V[a]==a) return a; return V[a]=root(V[a]); }
  int size(int a){ return Z[root(a)]; }
  void merge(int u,int v){ u=root(u); v=root(v); V[v]=u; if(u!=v)Z[u]+=Z[v]; }
};

int main(){
  int N,D,W; cin>>N>>D>>W;
  dsu A(N), B(N);
  set<pair<int,int>> S;
  rep(i,D){
    int u,v; cin>>u>>v; u--; v--;
    A.merge(u,v);
  }
  rep(i,W){
    int u,v; cin>>u>>v; u--; v--;
    B.merge(u,v);
  }

  rep(i,N){
    S.insert({A.root(i),B.root(i)});
  }

  LL ans=0;
  for(pair<int,int> p:S){
    LL zA = A.size(p.first);
    LL zB = B.size(p.second);
    ans += zA * zB;
  }
  cout<<(ans-N)<<endl;

  return 0;
}