結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-20 21:49:35 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 7,925 bytes |
コンパイル時間 | 2,343 ms |
コンパイル使用メモリ | 196,832 KB |
実行使用メモリ | 13,404 KB |
最終ジャッジ日時 | 2024-07-23 12:52:48 |
合計ジャッジ時間 | 4,039 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 56 ms
10,112 KB |
testcase_10 | AC | 55 ms
10,112 KB |
testcase_11 | AC | 55 ms
10,112 KB |
testcase_12 | AC | 57 ms
10,136 KB |
testcase_13 | AC | 55 ms
10,112 KB |
testcase_14 | AC | 44 ms
13,356 KB |
testcase_15 | AC | 43 ms
13,376 KB |
testcase_16 | AC | 48 ms
11,456 KB |
testcase_17 | AC | 51 ms
12,092 KB |
testcase_18 | AC | 36 ms
12,672 KB |
testcase_19 | AC | 35 ms
13,404 KB |
testcase_20 | AC | 35 ms
13,312 KB |
testcase_21 | AC | 31 ms
5,376 KB |
testcase_22 | AC | 31 ms
5,376 KB |
testcase_23 | AC | 30 ms
5,376 KB |
ソースコード
/* #region header */ #ifdef LOCAL #include "cxx-prettyprint-master/prettyprint.hpp" #define debug(x) cout << x << endl #else #define debug(...) 42 #endif #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; // types using ll = long long; using ull = unsigned long long; using ld = long double; typedef pair<ll, ll> Pl; typedef pair<int, int> Pi; typedef vector<ll> vl; typedef vector<int> vi; typedef vector<char> vc; template <typename T> using mat = vector<vector<T>>; typedef vector<vector<int>> vvi; typedef vector<vector<long long>> vvl; typedef vector<vector<char>> vvc; template <int mod> struct modint { int x; modint() : x(0) {} modint(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} modint& operator+=(const modint& p) { if ((x += p.x) >= mod) x -= mod; return *this; } modint& operator-=(const modint& p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } modint& operator*=(const modint& p) { x = (int)(1LL * x * p.x % mod); return *this; } modint& operator/=(const modint& p) { *this *= p.inverse(); return *this; } modint operator-() const { return modint(-x); } modint operator+(const modint& p) const { return modint(*this) += p; } modint operator-(const modint& p) const { return modint(*this) -= p; } modint operator*(const modint& p) const { return modint(*this) *= p; } modint operator/(const modint& p) const { return modint(*this) /= p; } bool operator==(const modint& p) const { return x == p.x; } bool operator!=(const modint& p) const { return x != p.x; } modint inverse() const { int a = x, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return modint(u); } modint pow(int64_t n) const { modint ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream& operator<<(ostream& os, const modint& p) { return os << p.x; } friend istream& operator>>(istream& is, modint& a) { int64_t t; is >> t; a = modint<mod>(t); return (is); } static int get_mod() { return mod; } }; // abreviations #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define rep_(i, a_, b_, a, b, ...) for (ll i = (a), max_i = (b); i < max_i; i++) #define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define rrep_(i, a_, b_, a, b, ...) \ for (ll i = (b - 1), min_i = (a); i >= min_i; i--) #define rrep(i, ...) rrep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define srep(i, a, b, c) for (ll i = (a), max_i = (b); i < max_i; i += c) #define SZ(x) ((int)(x).size()) #define pb(x) push_back(x) #define eb(x) emplace_back(x) #define mp make_pair //入出力 #define print(x) cout << x << endl template <class T> ostream& operator<<(ostream& os, const vector<T>& v) { for (auto& e : v) cout << e << " "; cout << endl; return os; } void scan(int& a) { cin >> a; } void scan(long long& a) { cin >> a; } void scan(char& a) { cin >> a; } void scan(double& a) { cin >> a; } void scan(string& a) { cin >> a; } template <class T> void scan(vector<T>& a) { for (auto& i : a) scan(i); } #define vsum(x) accumulate(all(x), 0LL) #define vmax(a) *max_element(all(a)) #define vmin(a) *min_element(all(a)) #define lb(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define ub(c, x) distance((c).begin(), upper_bound(all(c), (x))) // functions // gcd(0, x) fails. ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } 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; } template <typename T> T mypow(T x, ll n) { T ret = 1; while (n > 0) { if (n & 1) (ret *= x); (x *= x); n >>= 1; } return ret; } ll modpow(ll x, ll n, const ll mod) { ll ret = 1; while (n > 0) { if (n & 1) (ret *= x); (x *= x); n >>= 1; x %= mod; ret %= mod; } return ret; } uint64_t my_rand(void) { static uint64_t x = 88172645463325252ULL; x = x ^ (x << 13); x = x ^ (x >> 7); return x = x ^ (x << 17); } int popcnt(ull x) { return __builtin_popcountll(x); } // graph template template <typename T> struct edge { int src, to; T cost; edge(int to, T cost) : src(-1), to(to), cost(cost) {} edge(int src, int to, T cost) : src(src), to(to), cost(cost) {} edge& operator=(const int& x) { to = x; return *this; } bool operator<(const edge<T>& r) const { return cost < r.cost; } operator int() const { return to; } }; template <typename T> using Edges = vector<edge<T>>; template <typename T> using WeightedGraph = vector<Edges<T>>; using UnWeightedGraph = vector<vector<int>>; struct Timer { clock_t start_time; void start() { start_time = clock(); } int lap() { // return x ms. return (clock() - start_time) * 1000 / CLOCKS_PER_SEC; } }; /* #endregion*/ // constant #define inf 1000000000ll #define INF 4000000004000000000LL #define mod 1000000007ll using mint = modint<mod>; typedef vector<mint> vmint; typedef vector<vector<mint>> vvmint; #define endl '\n' const long double eps = 0.000000000000001; const long double PI = 3.141592653589793; // O(√m) // a^x = b (mod m)を満たすxの最小値(なければ-1) // x = p√m+r, p, r < √m // a^r = bA^p ll modlog(ll a, ll b, ll m) { //√m ll sqrt_m = sqrt(m) + 2; // a^-√m ll A = modpow(a, (mod - 2), mod); A = modpow(A, sqrt_m, mod); // a^0,...,a^√m unordered_map<ll, ll> a_pows; ll a_pow = 1; rep(i, sqrt_m + 1) { a_pows[a_pow] = i; a_pow *= a; a_pow %= m; } // A^0,...,A^√m ll A_pow = 1; rep(i, sqrt_m + 1) { if (a_pows.count(A_pow * b)) { return i * sqrt_m + a_pows[A_pow * b]; } A_pow *= A; A_pow %= m; } return -1; } int64_t euler_phi(int64_t n) { int64_t ret = n; for (int64_t i = 2; i * i <= n; i++) { if (n % i == 0) { ret -= ret / i; while (n % i == 0) n /= i; } } if (n > 1) ret -= ret / n; return ret; } /** * @brief UnionFind * @docs docs/UnionFind.md */ struct UnionFind { vector<int> data; // sizes of sets UnionFind(int sz) : data(sz, -1) {} bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) return false; if (data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return true; } int find(int k) { if (data[k] < 0) return k; return data[k] = find(data[k]); } int size(int k) { return (-data[find(k)]); } bool same(int x, int y) { return find(x) == find(y); } }; int main() { cin.tie(0); ios::sync_with_stdio(0); cout << setprecision(30) << fixed; int n, d, w; cin >> n >> d >> w; UnionFind bi(n), wa(n); rep(i, d) { int a, b; cin >> a >> b; a--; b--; bi.unite(a, b); } rep(i, w) { int c, d; cin >> c >> d; c--; d--; wa.unite(c, d); } ll ans = 0; vector<set<int>> root(n); rep(i, n) { root[bi.find(i)].insert(wa.find(i)); } rep(i, n) { if (i != bi.find(i)) continue; ll cnt = 0; for (int j : root[i]) { cnt += wa.size(j); } ans += cnt * bi.size(i); } print(ans - n); }