結果

問題 No.1293 2種類の道路
ユーザー ChanyuhChanyuh
提出日時 2020-11-21 19:13:33
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 226 ms / 2,000 ms
コード長 4,236 bytes
コンパイル時間 1,871 ms
コンパイル使用メモリ 148,296 KB
実行使用メモリ 16,556 KB
最終ジャッジ日時 2023-09-30 22:13:34
合計ジャッジ時間 5,370 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 140 ms
11,756 KB
testcase_10 AC 140 ms
11,480 KB
testcase_11 AC 144 ms
11,420 KB
testcase_12 AC 148 ms
11,480 KB
testcase_13 AC 142 ms
11,424 KB
testcase_14 AC 225 ms
15,928 KB
testcase_15 AC 226 ms
15,908 KB
testcase_16 AC 145 ms
13,544 KB
testcase_17 AC 161 ms
14,452 KB
testcase_18 AC 124 ms
15,124 KB
testcase_19 AC 218 ms
16,556 KB
testcase_20 AC 224 ms
16,556 KB
testcase_21 AC 34 ms
6,028 KB
testcase_22 AC 34 ms
5,960 KB
testcase_23 AC 34 ms
6,012 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 x 
    return 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();
}
0