結果

問題 No.1293 2種類の道路
コンテスト
ユーザー rin204
提出日時 2022-12-25 17:55:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,121 bytes
コンパイル時間 2,021 ms
コンパイル使用メモリ 209,680 KB
最終ジャッジ日時 2025-02-09 20:55:29
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 WA * 12
権限があれば一括ダウンロードができます

ソースコード

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);
	}

	int 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 += UF1.size(u) * 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