結果

問題 No.849 yuki国の分割統治
ユーザー beet
提出日時 2019-07-05 23:00:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,400 bytes
コンパイル時間 2,541 ms
コンパイル使用メモリ 212,208 KB
最終ジャッジ日時 2025-01-07 06:06:37
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 WA * 1
other AC * 7 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct UnionFind{
  int n,num;
  vector<int> r,p;
  UnionFind(){}
  UnionFind(int sz):n(sz),num(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
  int find(int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(int x,int y){
    return find(x)==find(y);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
    num--;
  }
  int size(int x){
    return r[find(x)];
  }
  int count() const{
    return num;
  }
};

//INSERT ABOVE HERE
signed main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  int n;
  cin>>n;
  vector<int> xs(n),ys(n);
  for(int i=0;i<n;i++) cin>>xs[i]>>ys[i];

  UnionFind uf(n);
  auto check=
    [&](int p,int q){
      using P = pair<int, int>;
      vector<P> vp;
      for(int i=0;i<n;i++)
        vp.emplace_back(xs[i]*q-ys[i]*p,i);
      sort(vp.begin(),vp.end());
      //for(auto p:vp) cout<<p.first<<" "<<p.second<<endl;

      for(int i=0;i<n;){
        int j=i;
        while(i<n&&vp[i].first==vp[j].first){
          uf.unite(vp[i].second,vp[j].second);
          i++;
        }
      }
    };
  check(a,b);
  check(c,d);

  {
    int gx=__gcd(a,c);
    int gy=__gcd(b,d);

    int dy=(gx==0?min(b,d):abs(b*(c/gx)-d*(a/gx)));
    int dx=(gy==0?min(a,c):abs(a*(d/gy)-c*(b/gy)));

    if(dy==0) dy=2e9;
    if(dx==0) dx=2e9;

    using P = pair<int, int>;
    map<P, int> mp;
    for(int i=0;i<n;i++){
      if(mp.count(P(xs[i]%dx,ys[i]%dy)))
        uf.unite(i,mp[P(xs[i]%dx,ys[i]%dy)]);

      if(mp.count(P((xs[i]+a)%dx,(ys[i]+b)%dy)))
        uf.unite(i,mp[P((xs[i]+a)%dx,(ys[i]+b)%dy)]);

      if(mp.count(P((xs[i]+c)%dx,(ys[i]+d)%dy)))
        uf.unite(i,mp[P((xs[i]+c)%dx,(ys[i]+d)%dy)]);

      mp[P(xs[i]%dx,ys[i]%dy)]=i;
    }
    mp.clear();
    for(int i=n-1;i>=0;i--){
      if(mp.count(P(xs[i]%dx,ys[i]%dy)))
        uf.unite(i,mp[P(xs[i]%dx,ys[i]%dy)]);

      if(mp.count(P((xs[i]+a)%dx,(ys[i]+b)%dy)))
        uf.unite(i,mp[P((xs[i]+a)%dx,(ys[i]+b)%dy)]);

      if(mp.count(P((xs[i]+c)%dx,(ys[i]+d)%dy)))
        uf.unite(i,mp[P((xs[i]+c)%dx,(ys[i]+d)%dy)]);

      mp[P(xs[i]%dx,ys[i]%dy)]=i;
    }
  }

  cout<<uf.count()<<endl;
  return 0;
}
0