結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-20 21:57:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 140 ms / 2,000 ms |
コード長 | 2,689 bytes |
コンパイル時間 | 1,689 ms |
コンパイル使用メモリ | 177,116 KB |
実行使用メモリ | 14,208 KB |
最終ジャッジ日時 | 2024-07-23 12:57:41 |
合計ジャッジ時間 | 4,449 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>#include <random>using namespace std; typedef unsigned long long _ulong; typedef long long int lint; typedef pair<lint, lint> plint; typedef pair<double long, doublelong> pld;#define ALL(x) (x).begin(), (x).end()#define SZ(x) ((lint)(x).size())#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)#define REP(i, n) FOR(i,0,n)#define IREP(i, n) IFOR(i,0,n)#define endk '\n'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; }lint gcd(lint a, lint b) { if (b == 0) return a; else return gcd(b, a % b); }lint ceil(lint a, lint b) { return (a + b - 1) / b; }lint digit(lint a) { return (lint)log10(a); }const lint MOD = 1e9 + 7, INF = 1e18;lint dx[8] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[8] = { 0, 1, 0, -1, -1, -1, 1, 1 };void YN(bool flag) { cout << (flag ? "YES" : "NO") << endk; }typedef pair<lint, string> Pa;typedef pair<lint, plint> tlint;template< typename T >class UnionFind {public:vector <T> par; // 各元の親を表す配列vector <T> siz; // 素集合のサイズを表す配列(1 で初期化)// ConstructorUnionFind(T sz_) : par(sz_), siz(sz_, 1ll) {for (T i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身}void init(T sz_) {par.resize(sz_);siz.assign(sz_, 1ll); // resize だとなぜか初期化されなかったfor (T i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身}// Member Function// FindT root(T x) { // 根の検索while (par[x] != x) {x = par[x] = par[par[x]]; // x の親の親を x の親とする}return x;}// Union(Unite, Merge)bool merge(T x, T y) {x = root(x);y = root(y);if (x == y) return false;// merge technique(データ構造をマージするテク.小を大にくっつける)if (siz[x] < siz[y]) swap(x, y);siz[x] += siz[y];par[y] = x;return true;}bool issame(T x, T y) { // 連結判定return root(x) == root(y);}T size(T x) { // 素集合のサイズreturn siz[root(x)];}};lint N, D, W, u, v;int main() {cin >> N >> D >> W;UnionFind<lint> drive(N), walk(N);vector<plint> edges(W);REP(i, D) {cin >> u >> v; u--; v--;drive.merge(u, v);}REP(i, W) {cin >> u >> v; u--; v--;walk.merge(u, v);}lint ans = 0;set<plint> used;REP(i, N) {plint p = { drive.root(i), walk.root(i) };if (!used.count(p)) {ans += drive.size(i) * walk.size(i);used.insert(p);}}cout << ans - N << endk;}