結果
問題 | No.1059 素敵な集合 |
ユーザー | kyoprouno |
提出日時 | 2020-05-22 22:59:38 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 2,146 bytes |
コンパイル時間 | 1,956 ms |
コンパイル使用メモリ | 179,732 KB |
実行使用メモリ | 7,932 KB |
最終ジャッジ日時 | 2023-09-30 15:32:21 |
合計ジャッジ時間 | 2,960 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
7,748 KB |
testcase_01 | AC | 34 ms
7,728 KB |
testcase_02 | AC | 7 ms
7,800 KB |
testcase_03 | AC | 5 ms
7,732 KB |
testcase_04 | AC | 5 ms
7,800 KB |
testcase_05 | AC | 5 ms
7,728 KB |
testcase_06 | AC | 7 ms
7,904 KB |
testcase_07 | AC | 7 ms
7,768 KB |
testcase_08 | AC | 8 ms
7,804 KB |
testcase_09 | AC | 5 ms
7,732 KB |
testcase_10 | AC | 10 ms
7,828 KB |
testcase_11 | AC | 7 ms
7,832 KB |
testcase_12 | AC | 6 ms
7,920 KB |
testcase_13 | AC | 9 ms
7,908 KB |
testcase_14 | AC | 5 ms
7,704 KB |
testcase_15 | AC | 14 ms
7,932 KB |
testcase_16 | AC | 7 ms
7,672 KB |
testcase_17 | AC | 7 ms
7,748 KB |
testcase_18 | AC | 5 ms
7,764 KB |
testcase_19 | AC | 32 ms
7,668 KB |
testcase_20 | AC | 31 ms
7,760 KB |
testcase_21 | AC | 13 ms
7,764 KB |
ソースコード
#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 pq priority_queue #define pb push_back #define eb emplace_back #define fi first #define se second #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; 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,0); rep(i,size){ makeSet(i); } } void makeSet(ll x){ //xだけが属する木を作る。 p[x]=x; rank[x]=0; sz[x]=x; } 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増える。 } } ll v=min(sz[x],sz[y]); sz[x]=sz[y]=v; } ll findSet(ll x){ //xが属する木の根の番号を返す if(x!=p[x]){ p[x]=findSet(p[x]); } return p[x]; } }; int main() { ll l,r; cin >> l >> r; DisjointSet ds=DisjointSet(200001); for(ll i=l;i<=r;i++){ for(ll j=2*i;j<=r;j+=i){ ds.unite(i,j); } } ll ans=0; for(ll i=l+1;i<=r;i++){ if(ds.sz[ds.findSet(i)]!=i) continue; else ans++; } cout << ans << endl; return 0; }