結果

問題 No.1293 2種類の道路
ユーザー 👑 rin204rin204
提出日時 2022-12-25 17:56:17
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 76 ms / 2,000 ms
コード長 3,128 bytes
コンパイル時間 2,527 ms
コンパイル使用メモリ 217,984 KB
実行使用メモリ 16,768 KB
最終ジャッジ日時 2024-11-19 07:32:25
合計ジャッジ時間 4,507 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,816 KB
testcase_09 AC 67 ms
11,184 KB
testcase_10 AC 66 ms
11,172 KB
testcase_11 AC 65 ms
11,184 KB
testcase_12 AC 66 ms
11,176 KB
testcase_13 AC 67 ms
11,176 KB
testcase_14 AC 41 ms
9,528 KB
testcase_15 AC 42 ms
9,680 KB
testcase_16 AC 62 ms
12,800 KB
testcase_17 AC 62 ms
12,928 KB
testcase_18 AC 54 ms
13,312 KB
testcase_19 AC 75 ms
16,640 KB
testcase_20 AC 76 ms
16,768 KB
testcase_21 AC 39 ms
6,824 KB
testcase_22 AC 39 ms
6,816 KB
testcase_23 AC 36 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "A.cpp"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl "\n"

void print(){
	cout << '\n';
}

template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
	cout << head;
	if (sizeof...(Tail)) cout << ' ';
  	print(forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> &A){
	int n = A.size();
	for(int i = 0; i < n; i++){
		cout << A[i];
		if(i == n - 1) cout << '\n';
		else cout << ' ';
	}
}

template<typename T, typename S>
void prisep(vector<T> &A, S sep){
	int n = A.size();
	for(int i = 0; i < n; i++){
		cout << A[i];
		if(i == n - 1) cout << '\n';
		else cout << sep;
	}
}

template<typename T>
void print(vector<vector<T>> &A){
	for(auto &row: A) print(row);
}

#line 3 "Library/C++/data_structure/RollbackUnionFind.hpp"
using namespace std;

struct RollbackUnionFind{
    int n;
    vector<int> par;
    int group;
    stack<pair<int, int>> history;
    int inner_snap;

    RollbackUnionFind(int n) : n(n){
        par.assign(n, -1);
        group = n;
        inner_snap = 0;
    }

    int find(int x){
        if(par[x] < 0) return x;
        else return find(par[x]);
    }

    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        history.push({x, par[x]});
        history.push({y, par[y]});
        if(x == y) return false;
        if(par[x] > par[y]) swap(x, y);
        group--;
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }

    int size(int x){
        return -par[find(x)];
    }

    vector<int> roots(){
        vector<int> ret;
        for(int i = 0; i < n; i++){
            if(i == find(i)) ret.push_back(i);
        }
        return ret;
    }

    void undo(){
        pair<int, int> tmp = history.top(); history.pop();
        int x = tmp.first;
        par[tmp.first] = tmp.second;
        tmp = history.top(); history.pop();
        par[tmp.first] = tmp.second;
        if(x != tmp.first) group++;
    }

    void snapshot(){
        inner_snap = (history.size()) >> 1;
    }

    int get_state(){
        return (history.size()) >> 1;
    }

    void rollback(int state=-1){
        if(state == -1) state = inner_snap;
        state <<= 1;
        assert(state <= history.size());
        while(state < history.size()) undo();
    }
};
#line 43 "A.cpp"

void solve(){
	int n, d, w;
	cin >> n >> d >> w;
	RollbackUnionFind UF1(n);
	RollbackUnionFind UF2(n);
	int a, b;
	for(int i = 0; i < d; i++){
		cin >> a >> b;
		UF1.unite(a - 1, b - 1);
	}
	for(int i = 0; i < w; i++){
		cin >> a >> b;
		UF2.unite(a - 1, b - 1);
	}

	ll ans = -n;
	map<int, vector<int>> mp;
	for(int i = 0; i < n; i++){
		mp[UF1.find(i)].push_back(i);
	}
	for(auto tmp:mp){
		auto group = tmp.second;
		int u = group[0];
		int ver = UF2.get_state();
		for(auto v:group){
			if(u == v) continue;
			UF2.unite(u, v);
		}
		ans += ll(UF1.size(u)) * ll(UF2.size(u));
		UF2.rollback(ver);
	}
	print(ans);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t;
    t = 1;
    // cin >> t;
    while(t--) solve();
	return 0;
}
0