結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-21 19:13:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 201 ms / 2,000 ms |
コード長 | 4,236 bytes |
コンパイル時間 | 1,950 ms |
コンパイル使用メモリ | 144,552 KB |
最終ジャッジ日時 | 2025-01-16 04:08:51 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include<iostream>#include<array>#include<string>#include<cstdio>#include<vector>#include<cmath>#include<algorithm>#include<functional>#include<iomanip>#include<queue>#include<ciso646>#include<random>#include<map>#include<set>#include<complex>#include<bitset>#include<stack>#include<unordered_map>#include<utility>#include<tuple>#include<cassert>using namespace std;typedef long long ll;typedef unsigned int ui;const ll mod = 1000000007;const ll INF = (ll)1000000007 * 1000000007;typedef pair<int, int> P;#define stop char nyaa;cin>>nyaa;#define rep(i,n) for(int i=0;i<n;i++)#define per(i,n) for(int i=n-1;i>=0;i--)#define Rep(i,sta,n) for(int i=sta;i<n;i++)#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)#define rep1(i,n) for(int i=1;i<=n;i++)#define per1(i,n) for(int i=n;i>=1;i--)#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)typedef long double ld;const ld eps = 1e-8;const ld pi = acos(-1.0);typedef pair<ll, ll> LP;int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};template<class T>bool chmax(T &a, const T &b) {if(a<b){a=b;return 1;}return 0;}template<class T>bool chmin(T &a, const T &b) {if(b<a){a=b;return 1;}return 0;}struct UnionFind {private:vector<int> par,ran;vector<int> edge,size;int n;public:UnionFind(int x){n=x;par.resize(n,0);ran.resize(n,0);edge.resize(n,0);size.resize(n,1);rep(i,n){par[i]=i;}}int find(int x) {if (par[x]==x)return x;else return par[x]=find(par[x]);}void unite(int x, int y) {x=find(x),y=find(y);if (x==y){edge[x]++;return;}if (ran[x]<ran[y]) {par[x]=y;size[y]+=size[x];edge[y]+=edge[x]+1;}else {par[y]=x;size[x]+=size[y];edge[x]+=edge[y]+1;if (ran[x]==ran[y])ran[x]++;}}bool same(int x,int y) {return find(x)==find(y);}int getSize(int x){return size[find(x)];}int getEdge(int x){return edge[find(x)];}};template<typename T>struct Compress{vector<T> V;Compress(){V.clear();}Compress(vector<T> &V):V(V){}void add(T x){V.push_back(x);}int build(){sort(V.begin(),V.end());V.erase(unique(V.begin(),V.end()),V.end());return V.size();}int get(T x){//get the index of the minimum element which is greater than xreturn lower_bound(V.begin(),V.end(),x)-V.begin();}pair<int, int> section(T l,T r){//get the range of indexes of [l,r)int l_=get(l),r_=get(r);return pair<int,int>(l_,r_);}T &operator [] (int i) {return V[i];};};int n,d,w;P e[400010];ll S[200010];Compress<int> comp1,comp2;map<P,bool> is_connected;void solve(){cin >> n >> d >> w;UnionFind uf1(n),uf2(n);rep(i,d){int a,b;cin >> a >> b;a--;b--;uf1.unite(a,b);e[i]=P(a,b);}rep(i,n){comp1.add(uf1.find(i));}rep(i,w){int a,b;cin >> a >> b;a--;b--;uf2.unite(a,b);e[i+d]=P(a,b);}rep(i,n){comp2.add(uf2.find(i));}int Z=comp1.build();comp2.build();rep(i,d+w){int v=comp1.get(uf1.find(e[i].first)),u=comp2.get(uf2.find(e[i].second));if(!is_connected[P(v,u)]) {is_connected[P(v,u)]=true;S[v]+=uf2.getSize(comp2[u]);}v=comp1.get(uf1.find(e[i].second)),u=comp2.get(uf2.find(e[i].first));if(!is_connected[P(v,u)]) {is_connected[P(v,u)]=true;S[v]+=uf2.getSize(comp2[u]);}}rep(i,n){int v=comp1.get(uf1.find(i)),u=comp2.get(uf2.find(i));if(!is_connected[P(v,u)]) {is_connected[P(v,u)]=true;S[v]+=uf2.getSize(comp2[u]);}}ll ans=0;rep(i,Z){//cout << i << " " << uf1.getSize(comp1[i]) << " " << S[i] << endl;ll T=uf1.getSize(comp1[i]);ans+=T*(S[i]-T);ans+=T*(T-1);}cout << ans << endl;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(50);solve();}