結果
問題 | No.1293 2種類の道路 |
ユーザー |
![]() |
提出日時 | 2020-11-20 23:57:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 169 ms / 2,000 ms |
コード長 | 2,973 bytes |
コンパイル時間 | 2,555 ms |
コンパイル使用メモリ | 198,856 KB |
実行使用メモリ | 25,524 KB |
最終ジャッジ日時 | 2024-07-23 14:05:18 |
合計ジャッジ時間 | 5,394 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:114:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 114 | for(auto [x,y]:s[i]){ | ^ main.cpp:118:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 118 | for(auto [x,y]:m){ | ^
ソースコード
#pragma GCC optimize("O3")#include <bits/stdc++.h>#define ll long long#define rep(i,n) for(ll i=0;i<(n);i++)#define pll pair<ll,ll>#define pii pair<int,int>#define pq priority_queue#define pb push_back#define eb emplace_back#define fi first#define se second#define endl '\n'#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))using namespace std;inline int topbit(unsigned long long x){return x?63-__builtin_clzll(x):-1;}inline int popcount(unsigned long long x){return __builtin_popcountll(x);}inline int parity(unsigned long long x){//popcount%2return __builtin_parity(x);}template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}const ll INF=1e9+7;class DisjointSet{public:vector<ll> rank,p,sz;DisjointSet(){}DisjointSet(ll size){ //作られうる木の頂点数の最大値を入れる。rank.resize(size,0);p.resize(size,0);sz.resize(size,1);rep(i,size) makeSet(i);}void makeSet(ll x){ //xだけが属する木を作る。p[x]=x;rank[x]=0;}bool same(ll x,ll y){ //xとyが同じ木に属するかどうかreturn findSet(x)==findSet(y);}void unite(ll x, ll y){link(findSet(x),findSet(y));}void link(ll x, ll y){ //rankが大きい方の根に小さい方の根をつける。if(rank[x]>rank[y]){p[y]=x;}else{p[x]=y;if(rank[x]==rank[y]){rank[y]++; //xとyの木のrankが同じであれば、統合するとrankが1増える。}}sz[x]+=sz[y];sz[y]=sz[x];}ll findSet(ll x){ //xが属する木の根の番号を返すif(x!=p[x]){p[x]=findSet(p[x]);}return p[x];}};int main(){ll n,D,w;cin >> n >>D >> w;vector<ll> a(D),b(D);vector<ll> c(w),d(w);DisjointSet ds1=DisjointSet(n+1);DisjointSet ds2=DisjointSet(n+1);rep(i,D){cin >> a[i] >> b[i];a[i]--;b[i]--;if(!ds1.same(a[i],b[i])){ds1.unite(a[i],b[i]);}}rep(i,w){cin >> c[i] >> d[i];c[i]--;d[i]--;if(!ds2.same(c[i],d[i])){ds2.unite(c[i],d[i]);}}vector<set<pll>> s(n);rep(i,n){ll p1=ds1.findSet(i);ll p2=ds2.findSet(i);s[p1].insert({i,p2});}ll ans=0;rep(i,n){map<ll,ll> m;ll sum=0;for(auto [x,y]:s[i]){m[y]++;}ll all=s[i].size();for(auto [x,y]:m){sum+=ds2.sz[x];}ans+=sum*all;}ans-=n;cout << ans << endl;}