#528025 (C++14) No.1059 素敵な集合

• 問題: No.1059 素敵な集合
• ユーザー: tonegawa
• 提出日時: 2020-08-11 10:19:56
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 13 ms / 2,000 ms
• コード長: 1,591 bytes
• コンパイル時間: 954 ms
• コンパイル使用メモリ: 99,096 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-07-23 09:40:39
• 合計ジャッジ時間: 1,886 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	4 ms; 6,812 KB
testcase_01	AC	13 ms; 6,940 KB
testcase_02	AC	5 ms; 6,940 KB
testcase_03	AC	4 ms; 6,940 KB
testcase_04	AC	4 ms; 6,944 KB
testcase_05	AC	4 ms; 6,940 KB
testcase_06	AC	5 ms; 6,940 KB
testcase_07	AC	5 ms; 6,940 KB
testcase_08	AC	6 ms; 6,940 KB
testcase_09	AC	4 ms; 6,940 KB
testcase_10	AC	6 ms; 6,940 KB
testcase_11	AC	6 ms; 6,944 KB
testcase_12	AC	5 ms; 6,940 KB
testcase_13	AC	7 ms; 6,940 KB
testcase_14	AC	4 ms; 6,944 KB
testcase_15	AC	9 ms; 6,944 KB
testcase_16	AC	5 ms; 6,944 KB
testcase_17	AC	5 ms; 6,940 KB
testcase_18	AC	4 ms; 6,940 KB
testcase_19	AC	13 ms; 6,944 KB
testcase_20	AC	13 ms; 6,940 KB
testcase_21	AC	9 ms; 6,940 KB

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

struct UF{
  std::vector<int> par, dep, sz;
  UF(int n){
    par.resize(n+1), dep.resize(n+1), sz.resize(n+1);
    init(n);
  }
  void init(int nu) {
    for(int iu=0;iu<=nu;iu++){
      par[iu] = iu;
      dep[iu] = 0;
      sz[iu] = 1;
    }
  }
  int find(int xu){
    if(par[xu] == xu) return xu;
    return par[xu] = find(par[xu]);
  }
  void unite(int xu, int yu){
    xu=find(xu);
    yu=find(yu);
    if(xu == yu) return;
    if(dep[xu] < dep[yu]){
      sz[yu] += sz[xu];
      par[xu] = yu;
    }else{
      par[yu] = xu;
      sz[xu] += sz[yu];
      if(dep[xu] == dep[yu]) dep[xu]++;
    }
  }
  bool same(int xu, int yu){ return find(xu) == find(yu);}
  int get_size(int x){return sz[find(x)];}
};
int main(int argc, char const *argv[]) {
  ll L, R;std::cin >> L >> R;
  UF uf(200001);
  for(ll i=L;i<=R;i++){
    for(ll j=2*i;j<=R;j+=i) {
      uf.unite(i, j);
    }
  }
  //これ以上上がなく
  ll ans = 0;
  for(int i=L;i<=R;i++) if(uf.find(i)==i) ans++;
  std::cout << ans-1 << '\n';
  return 0;
}