結果

問題 No.2319 Friends+
コンテスト
ユーザー eQe
提出日時 2025-03-18 07:18:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,623 ms / 3,000 ms
コード長 7,286 bytes
コンパイル時間 6,890 ms
コンパイル使用メモリ 333,240 KB
実行使用メモリ 53,312 KB
最終ジャッジ日時 2025-03-18 07:18:39
合計ジャッジ時間 33,358 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
namespace my{
#define eb emplace_back
#define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__)
#define RDVL(T,n,...) vec<T>__VA_ARGS__;resizes({n},__VA_ARGS__);lin(__VA_ARGS__)
#define RDVV(T,n,...) vec<T>__VA_ARGS__;resizes({n},__VA_ARGS__);vin(__VA_ARGS__)
#define VL(n,...) RDVL(ll,n,__VA_ARGS__)
#define VV(n,...) RDVV(ll,n,__VA_ARGS__)
#define FO(n) for(ll ij=n;ij-->0;)
#define FOR(i,...) for(auto[i,i##stop,i##step]=range(0,__VA_ARGS__);i<i##stop;i+=i##step)
#define fo(i,...) FO##__VA_OPT__(R)(i __VA_OPT__(,__VA_ARGS__))
#define of(i,...) for(auto[i,i##stop,i##step]=range(1,__VA_ARGS__);i>=i##stop;i+=i##step)
#define fe(a,e,...) for(auto&&__VA_OPT__([)e __VA_OPT__(,__VA_ARGS__]):a)
#define bit_sizeof(T) ll(sizeof(T)*CHAR_BIT)
#define schrodinger(p,c) (p?c:remove_cvref_t<decltype(c)>{})
#define do_continue(...) {__VA_ARGS__;continue;}
#define do_break(...) {__VA_ARGS__;break;}
#define base_operator(op,type) auto operator op(const type&v)const{auto copy=*this;return copy op##=v;}
#define single_testcase void solve();}int main(){my::io();my::solve();}namespace my{
void io(){cerr<<endl;cin.tie(nullptr)->sync_with_stdio(0);cout<<fixed<<setprecision(15);}
using ll=long long;
constexpr auto range(ll s,ll b){ll a=0;if(s)swap(a,b);return array{a-s,b,1-s*2};}
constexpr auto range(ll s,ll a,ll b,ll c=1){return array{a-s,b,(1-s*2)*c};}
const string newline{char(10)};
const string space{char(32)};
constexpr auto Yes(bool p=1){return p?"Yes":"No";}
constexpr auto No(){return"No";}

template<class...A>using pack_back_t=tuple_element_t<sizeof...(A)-1,tuple<A...>>;

template<class V>concept vectorial=is_base_of_v<vector<typename remove_cvref_t<V>::value_type>,remove_cvref_t<V>>;
template<class V>constexpr int rank(){if constexpr(vectorial<V>)return rank<typename V::value_type>()+1;else return 0;}
template<class T>struct core_t_helper{using core_t=T;};
template<vectorial V>struct core_t_helper<V>{using core_t=typename core_t_helper<typename V::value_type>::core_t;};
template<class T>using core_t=core_t_helper<T>::core_t;
template<class V>istream&operator>>(istream&i,vector<V>&v){fe(v,e)i>>e;return i;}
template<class V>ostream&operator<<(ostream&o,const vector<V>&v){ll n=v.size();fo(i,n)o<<v[i]<<schrodinger(i<n-1,vectorial<V>?newline:space);return o;}

template<class V>struct vec;
template<int rank,class T>struct tensor_helper{using type=vec<typename tensor_helper<rank-1,T>::type>;};
template<class T>struct tensor_helper<0,T>{using type=T;};
template<int rank,class T>using tensor=typename tensor_helper<rank,T>::type;

template<class V>struct vec:vector<V>{
  static constexpr int R=rank<vec<V>>();
  using C=core_t<V>;
  using vector<V>::vector;
  vec(const vector<V>&v){vector<V>::operator=(v);}

  vec(const auto&...a)requires(sizeof...(a)>=3){resizes(a...);}
  void resizes(const auto&...a){*this=make(a...);}
  static auto make(ll n,const auto&...a){if constexpr(sizeof...(a)==1)return vec<C>(n,array{a...}[0]);else return vec<decltype(make(a...))>(n,make(a...));}

  vec&operator^=(const vec&u){this->insert(this->end(),u.begin(),u.end());return*this;}
  vec&operator+=(const vec&u){vec&v=*this;assert(v.size()==u.size());fo(i,v.size())v[i]+=u[i];return v;}
  vec&operator-=(const vec&u){vec&v=*this;assert(v.size()==u.size());fo(i,v.size())v[i]-=u[i];return v;}
  base_operator(^,vec)
  base_operator(+,vec)
  base_operator(-,vec)

  vec&operator++(){fe(*this,e)++e;return*this;}
  vec&operator--(){fe(*this,e)--e;return*this;}

  ll size()const{return vector<V>::size();}

  inline ll w()const requires(R==2){return (*this)[0].size();}
};
template<class...A>requires(sizeof...(A)>=2)vec(const A&...a)->vec<tensor<sizeof...(A)-2,pack_back_t<A...>>>;
vec(ll)->vec<ll>;

template<class...A>void resizes(const array<ll,common_type_t<A...>::R+1>&s,A&...a){(apply([&](const auto&...b){a.resizes(b...); },s),...);}

void lin(auto&...a){(cin>>...>>a);}
void vin(auto&...a){fo(i,(a.size()&...))(cin>>...>>a[i]);}
void pp(const auto&...a){ll n=sizeof...(a);((cout<<a<<schrodinger(--n>0,space)),...);cout<<newline;}

void dec(auto&...a){((--a),...);}

constexpr uint64_t kth_root_floor(uint64_t a,ll k){
  if (k==1)return a;
  auto within=[&](uint32_t x){uint64_t t=1;fo(k)if(__builtin_mul_overflow(t,x,&t))return false;return t<=a;};

  uint64_t r=0;
  of(i,bit_sizeof(uint32_t))if(within(r|(1u<<i)))r|=1u<<i;
  return r;
}
constexpr auto sqrt_floor(auto x){return kth_root_floor(x,2);}

template<class WT>struct edge{
  int from,to;
  WT wt;
  int id;
  edge()=default;
  edge(int from,int to,WT wt=1,int id=-1):from(from),to(to),wt(wt),id(id){}
  auto operator<=>(const edge&e)const{return wt<=>e.wt;}
  friend ostream&operator<<(ostream&o,const edge&e){return o<<"(to "<<e.to<<", wt "<<e.wt<<",id "<<e.id<<")";}
};

template<class WT>struct graph{
  vec<vec<edge<WT>>>edges;

  graph()=default;
  graph(ll n):edges(n){}

  decltype(auto)operator[](ll i){return edges[i];}
  decltype(auto)operator[](ll i)const{return edges[i];}
  ll size()const{return edges.size();}

  friend ostream&operator<<(ostream&o,const graph&g){
    fo(u,g.size()){
      o<<"from "<<u<<": ";
      fo(j,g[u].size())o<<g[u][j]<<schrodinger(j!=g[u].size()-1,space);
      o<<newline;
    }
    return o;
  }

  auto&add_edges(const vec<ll>&p){fo(i,p.size())if(p[i]!=-1)edges[p[i]].eb(p[i],i,1,i);return*this;}
  auto&add_edges(const vec<ll>&a,const vec<ll>&b){fo(i,a.size())edges[a[i]].eb(a[i],b[i],1,i);return*this;}
  auto&add_edges(const vec<ll>&a,const vec<ll>&b,const vec<WT>&w){fo(i,a.size())edges[a[i]].eb(a[i],b[i],w[i],i);return*this;}
  auto&add_edges(const vec<edge<WT>>&es){fe(es,e)edges[e.from].eb(e);return*this;}

  vec<edge<WT>>get_edges()const{
    vec<edge<WT>>res;
    fo(u,size())fe(edges[u],e)res.eb(e);
    return res;
  }
};

template<class WT>auto sparse_dense_decomposition(const graph<WT>&g){
  ll L=sqrt_floor(g.get_edges().size());
  ll N=g.size();

  vec<bool>is_sparse(N);
  graph<WT>sparse_sparse(N),sparse_dense(N),dense_sparse(N),dense_dense(N);
  fo(u,N){
    is_sparse[u]=(g[u].size()<L);
    fe(g[u],e){
      if(is_sparse[u])(g[e.to].size()<L?sparse_sparse:sparse_dense)[u].eb(e);
      else (g[e.to].size()<L?dense_sparse:dense_dense)[u].eb(e);
    }
  }
  return tuple{is_sparse,sparse_sparse,sparse_dense,dense_sparse,dense_dense};
}

single_testcase
void solve(){
  LL(N,M);
  VL(N,pos);--pos;
  VV(M,a,b);dec(a,b);

  graph<ll>g(N);
  g.add_edges(a,b).add_edges(b,a);

  auto[is_sparse,ssg,sdg,dsg,ddg]=sparse_dense_decomposition(g);

  vec belong(N,unordered_map<ll,ll>{}); // belong[i][u]:densuな頂点uについて，ワールドiに属するuのフレンド数．
  fo(u,N)if(!is_sparse[u])fe(g[u],e)belong[pos[e.to]][u]++;

  LL(Q);
  fo(Q){
    LL(u,v);dec(u,v);
    if(pos[u]==pos[v])do_continue(pp(No()));

    if(is_sparse[u]){
      ll ok=0;
      fe(g[u],e)if(pos[e.to]==pos[v])do_break(ok=1);
      if(!ok)do_continue(pp(No()));

      pp(Yes());
      fe(sdg[u],e){
        belong[pos[v]][e.to]++;
        belong[pos[u]][e.to]--;
      }
      pos[u]=pos[v];
    }else{
      if(belong[pos[v]][u]==0)do_continue(pp(No()));

      pp(Yes());
      fe(ddg[u],e){
        belong[pos[v]][e.to]++;
        belong[pos[u]][e.to]--;
      }
      pos[u]=pos[v];
    }
  }
}}
0