結果
問題 | No.1293 2種類の道路 |
ユーザー |
|
提出日時 | 2020-11-20 22:03:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 4,907 bytes |
コンパイル時間 | 2,416 ms |
コンパイル使用メモリ | 204,184 KB |
最終ジャッジ日時 | 2025-01-16 02:21:26 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for(int i = 0; i < n; i++)#define rep2(i, x, n) for(int i = x; i <= n; i++)#define rep3(i, x, n) for(int i = x; i >= n; i--)#define each(e, v) for(auto &e: v)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;#define pq(type, name) priority_queue<type> name#define iq(type, name) priority_queue<type, vector<type>, greater<type>> nameconst int inf = (1<<30)-1;const ll INF = (1LL<<60)-1;const double pi = acos(-1.0);const double EPS = 1e-10;template<typename T> bool chmax(T &x, const T &y){if(x < y) {x = y; return true;}return false;}template<typename T> bool chmin(T &x, const T &y){if(x > y) {x = y; return true;}return false;}void in() {}template<typename Head, typename ...Tail> void in(Head &&head, Tail &&...tail){cin >> head;in(forward<Tail>(tail)...);}void out() {cout << '\n';}template<typename Head, typename ...Tail> void out(Head &&head, Tail &&...tail){cout << head << ' ';out(forward<Tail>(tail)...);}void outn() {}template<typename Head, typename ...Tail> void outn(Head &&head, Tail &&...tail){cout << head << '\n';outn(forward<Tail>(tail)...);}template<typename T, typename U> void in(pair<T, U> &p){cin >> p.first >> p.second;}template<typename T, typename U> void out(pair<T, U> p){cout << p.first << ' ' << p.second << '\n';}using vi = vector<int>;using vll = vector<ll>;#define vec1(type, name, ...) vector<type> name(__VA_ARGS__)#define VEC1(type, ...) vector<type>(__VA_ARGS__)#define vec2(type, name, a, ...) vector<vector<type>> name(a, VEC1(type, __VA_ARGS__))#define VEC2(type, a, ...) vector<vector<type>>(a, VEC1(type, __VA_ARGS__))#define vec3(type, name, a, b, ...) vector<vector<vector<type>>> name(a, VEC2(type, b, __VA_ARGS__))#define VEC3(type, a, b, ...) vector<vector<vector<type>>>(a, VEC2(type, b, __VA_ARGS__))#define vec4(type, name, a, b, c, ...) vector<vector<vector<vector<type>>>> name(a, VEC3(type, b, c, __VA_ARGS__))#define VEC4(type, a, b, c, ...) vector<vector<vector<vector<type>>>>(a, VEC3(type, b, c, __VA_ARGS__))#define vec5(type, name, a, b, c, d, ...) vector<vector<vector<vector<vector<type>>>>> name(a, VEC4(type, b, c, d, __VA_ARGS__))#define VEC5(type, a, b, c, d, ...) vector<vector<vector<vector<vector<type>>>>>(a, VEC4(type, b, c, d, __VA_ARGS__))template<typename T> void vin(vector<T> &a){rep(i, sz(a)) cin >> a[i];}template<typename T> void vout(const vector<T> &a){for(auto &e: a) cout << e << ' ';cout << '\n';}template<typename T> void voutn(const vector<T> &a){for(auto &e: a) cout << e << '\n';}template<typename T> void unique(vector<T> &a){sort(all(a)), a.erase(unique(all(a)), a.end());}vector<int> iota(int n){vector<int> ret(n);iota(all(ret), 0);return ret;}template<typename T> vector<int> iota(const vector<T> &a, bool greater = false){vector<int> ret = iota(sz(a));sort(all(ret), [&](int i, int j){return (a[i] < a[j])^greater;});return ret;}struct io_setup{io_setup(){ios_base::sync_with_stdio(false);cin.tie(NULL);cout << fixed << setprecision(15);}} io_setup;#define VEC(type, name, n) vector<type> name(n); vin(name)#define INT(...) int __VA_ARGS__; in(__VA_ARGS__)#define LL(...) ll __VA_ARGS__; in(__VA_ARGS__)#define CHAR(...) char __VA_ARGS__; in(__VA_ARGS__)#define STR(...) string __VA_ARGS__; in(__VA_ARGS__)#define DBL(...) double __VA_ARGS__; in(__VA_ARGS__)const int MOD = 1000000007;//const int MOD = 998244353;struct Union_Find_Tree{vector<int> data;const int n;Union_Find_Tree(int n) : n(n){data.assign(n, -1);}int root(int x){if(data[x] < 0) return x;return data[x] = root(data[x]);}bool unite(int x, int y){x = root(x), y = root(y);if(x == y) return false;if(data[x] > data[y]) swap(x, y);data[x] += data[y], data[y] = x;return true;}int size(int x) {return -data[root(x)];}bool same(int x, int y) {return root(x) == root(y);}void clear() {fill(all(data), -1);}};int main(){INT(N, D, W);Union_Find_Tree uf1(N), uf2(N);while(D--){INT(u, v); u--, v--;uf1.unite(u, v);}while(W--){INT(u, v); u--, v--;uf2.unite(u, v);}vi ans[N];rep(i, N){int j = uf2.root(i);ans[j].eb(uf1.root(i));}ll sum = 0;rep(i, N){unique(ans[i]);ll k = uf2.size(i);each(e, ans[i]) sum += k*uf1.size(e);}out(sum-N);}