結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2021-03-08 11:46:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 175 ms / 2,000 ms |
コード長 | 2,739 bytes |
コンパイル時間 | 2,201 ms |
コンパイル使用メモリ | 204,420 KB |
最終ジャッジ日時 | 2025-01-19 12:54:18 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include "bits/stdc++.h"#define MOD 1000000007#define rep(i, n) for(ll i=0; i < (n); i++)#define rrep(i, n) for(ll i=(n)-1; i >=0; i--)#define ALL(v) v.begin(),v.end()#define rALL(v) v.rbegin(),v.rend()#define FOR(i, j, k) for(ll i=j;i<k;i++)#define debug_print(var) cerr << #var << "=" << var <<endl;#define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" "#define fi first#define se secondusing namespace std;typedef long long int ll;typedef vector<ll> llvec;typedef vector<double> dvec;typedef pair<ll, ll> P;typedef long double ld;struct edge{ll x, c;};struct UnionFind{ll N;llvec p;llvec cnt;UnionFind(ll n){N = n;p=llvec(N);cnt=llvec(N, 0);rep(i, N){p[i] = i;cnt[i] = 1;}}void con(ll a, ll b){P at = root(a);P bt = root(b);if(at.second!=bt.second){if(at.first>bt.first){swap(at, bt);swap(a, b);}p[at.second] = bt.second;cnt[bt.second]+=cnt[at.second];p[a]=bt.second;}}P root(ll a){ll atmp = a;ll c=0;while(atmp!=p[atmp]){atmp = p[atmp];c++;}p[a] = atmp;return {c, atmp};}bool is_con(ll a, ll b){P at=root(a);P bt=root(b);return at.second == bt.second;}};struct UnionFind2{ll N;llvec p;llvec cnt;vector<set<ll>> type;UnionFind2(ll n){N = n;p=llvec(N);cnt=llvec(N, 0);type=vector<set<ll>>(N);rep(i, N){p[i] = i;cnt[i] = 1;}}void con(ll a, ll b){P at = root(a);P bt = root(b);if(at.second!=bt.second){if(cnt[at.se]>cnt[bt.se])swap(at,bt);p[at.second] = bt.second;cnt[bt.second]+=cnt[at.second];for(auto is: type[at.se]){type[bt.se].insert(is);}p[a]=bt.second;}}P root(ll a){ll atmp = a;ll c=0;while(atmp!=p[atmp]){atmp = p[atmp];c++;}p[a] = atmp;return {c, atmp};}bool is_con(ll a, ll b){P at=root(a);P bt=root(b);return at.second == bt.second;}};/**************************************** A main function starts from here *****************************************/int main(){ll N, D, W;cin >> N >> D >> W;UnionFind uf1(N);UnionFind2 uf2(N);rep(i, D){ll a, b;cin >> a >> b;a--;b--;uf1.con(a, b);}rep(i, N){auto p = uf1.root(i);uf2.type[i].insert(p.se);}rep(i, W){ll a, b;cin >> a >> b;a--;b--;uf2.con(a, b);}ll ans = 0;rep(i, N){if(uf2.p[i]==i){for(auto is: uf2.type[i]){ans = ans + uf1.cnt[is] * uf2.cnt[i];}}}cout << ans-N << endl;return 0;}