結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-20 21:27:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 177 ms / 2,000 ms |
コード長 | 1,592 bytes |
コンパイル時間 | 1,935 ms |
コンパイル使用メモリ | 182,956 KB |
実行使用メモリ | 21,440 KB |
最終ジャッジ日時 | 2024-07-23 12:38:48 |
合計ジャッジ時間 | 5,229 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main(){int N, D, W;cin >> N >> D >> W;vector<vector<int>> E1(N);for (int i = 0; i < D; i++){int a, b;cin >> a >> b;a--;b--;E1[a].push_back(b);E1[b].push_back(a);}vector<vector<int>> E2(N);for (int i = 0; i < W; i++){int c, d;cin >> c >> d;c--;d--;E2[c].push_back(d);E2[d].push_back(c);}vector<int> c1(N, -1);int cnt1 = 0;for (int i = 0; i < N; i++){if (c1[i] == -1){c1[i] = cnt1;queue<int> Q;Q.push(i);while (!Q.empty()){int v = Q.front();Q.pop();for (int w : E1[v]){if (c1[w] == -1){c1[w] = cnt1;Q.push(w);}}}cnt1++;}}vector<int> c2(N, -1);int cnt2 = 0;vector<int> sz;for (int i = 0; i < N; i++){if (c2[i] == -1){c2[i] = cnt2;int cnt = 1;queue<int> Q;Q.push(i);while (!Q.empty()){int v = Q.front();Q.pop();for (int w : E2[v]){if (c2[w] == -1){c2[w] = cnt2;cnt++;Q.push(w);}}}sz.push_back(cnt);cnt2++;}}vector<set<int>> st(cnt1);for (int i = 0; i < N; i++){st[c1[i]].insert(c2[i]);}vector<int> ans(cnt1, 0);for (int i = 0; i < cnt1; i++){for (int j : st[i]){ans[i] += sz[j];}}long long sum = 0;for (int i = 0; i < N; i++){sum += ans[c1[i]];}sum -= N;cout << sum << endl;}