結果
問題 | No.1293 2種類の道路 |
ユーザー |
|
提出日時 | 2020-11-20 22:46:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 66 ms / 2,000 ms |
コード長 | 2,164 bytes |
コンパイル時間 | 1,103 ms |
コンパイル使用メモリ | 98,024 KB |
実行使用メモリ | 16,564 KB |
最終ジャッジ日時 | 2024-07-23 13:31:20 |
合計ジャッジ時間 | 2,912 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include<iostream>#include<string>#include<iomanip>#include<cmath>#include<vector>#include<algorithm>#include<utility>#include<set>using namespace std;#define int long long#define endl "\n"constexpr long long INF = (long long)1e18;constexpr long long MOD = 1'000'000'007;struct fast_io {fast_io(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);};} fio;class union_find{int _setnum;vector<int> par, nume;public:union_find(){}union_find(int x){par.resize(x);nume.resize(x);init();}~union_find(){//}void clear(){_setnum = 0;par.clear();nume.clear();}void init(){_setnum = par.size();for(int i = 0; i < par.size(); i++){par[i] = i;nume[i] = 1;}}void resize(int x){par.resize(x);nume.resize(x);init();}int find(int x){return par[x] == x ? x : par[x] = find(par[x]);}void unite(int x, int y){x = find(x);y = find(y);if(x == y)return;_setnum--;if(nume[x] > nume[y]) std::swap(x,y);par[x] = y;nume[y] += nume[x];}bool same(int x, int y){return find(x) == find(y);}int numel(int x){return nume[find(x)];}int size(){return par.size();}int setnum(){return _setnum;}};signed main(){cout<<fixed<<setprecision(10);int N;int D, W;int ans = 0;vector<set<int>> vs;vector<int> sum;union_find uf, uf2;cin>>N>>D>>W;uf.resize(N);uf2.resize(N);vs.resize(N);sum.resize(N);for(int i = 0; i < D; i++){int a, b;cin>>a>>b;a--, b--;uf.unite(a, b);}for(int i = 0; i < W; i++){int a, b;cin>>a>>b;a--, b--;uf2.unite(a, b);}for(int i = 0; i < N; i++){if(vs[uf2.find(i)].count(uf.find(i)) == 0) {sum[uf2.find(i)] += uf.numel(i);vs[uf2.find(i)].insert(uf.find(i));}}for(int i = 0; i < N; i++){ans += sum[uf2.find(i)];}ans -= N;cout<<ans<<endl;return 0;}