제출 #854199

#제출 시각아이디문제언어결과실행 시간메모리
854199maroonrk수천개의 섬 (IOI22_islands)C++17
1.75 / 100
28 ms7892 KiB
#include "islands.h" #ifndef LOCAL #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #endif #include <bits/stdc++.h> using namespace std; using ll=long long; //#define int ll #define rng(i,a,b) for(int i=int(a);i<int(b);i++) #define rep(i,b) rng(i,0,b) #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #define si(x) int(x.size()) #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl #else #define dmp(x) void(0) #endif template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;} template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;} template<class t> using vc=vector<t>; template<class t> using vvc=vc<vc<t>>; using pi=pair<int,int>; using vi=vc<int>; template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p){ return os<<"{"<<p.a<<","<<p.b<<"}"; } template<class t> ostream& operator<<(ostream& os,const vc<t>& v){ os<<"{"; for(auto e:v)os<<e<<","; return os<<"}"; } #define mp make_pair #define mt make_tuple #define one(x) memset(x,-1,sizeof(x)) #define zero(x) memset(x,0,sizeof(x)) #ifdef LOCAL void dmpr(ostream&os){os<<endl;} template<class T,class... Args> void dmpr(ostream&os,const T&t,const Args&... args){ os<<t<<" "; dmpr(os,args...); } #define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__) #else #define dmp2(...) void(0) #endif using uint=unsigned; using ull=unsigned long long; template<class t,size_t n> ostream& operator<<(ostream&os,const array<t,n>&a){ return os<<vc<t>(all(a)); } template<int i,class T> void print_tuple(ostream&,const T&){ } template<int i,class T,class H,class ...Args> void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<<get<i>(t); print_tuple<i+1,T,Args...>(os,t); } template<class ...Args> ostream& operator<<(ostream&os,const tuple<Args...>&t){ os<<"{"; print_tuple<0,tuple<Args...>,Args...>(os,t); return os<<"}"; } ll read(){ ll i; cin>>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } pi readpi(int off=0){ int a,b;cin>>a>>b; return pi(a+off,b+off); } template<class t> void print_single(t x,int suc=1){ cout<<x; if(suc==1) cout<<"\n"; if(suc==2) cout<<" "; } template<class t,class u> void print_single(const pair<t,u>&p,int suc=1){ print_single(p.a,2); print_single(p.b,suc); } template<class T> void print_single(const vector<T>&v,int suc=1){ rep(i,v.size()) print_single(v[i],i==int(v.size())-1?suc:2); } template<class T> void print_offset(const vector<T>&v,ll off,int suc=1){ rep(i,v.size()) print_single(v[i]+off,i==int(v.size())-1?suc:2); } template<class T,size_t N> void print_single(const array<T,N>&v,int suc=1){ rep(i,N) print_single(v[i],i==int(N)-1?suc:2); } template<class T> void print(const T&t){ print_single(t); } template<class T,class ...Args> void print(const T&t,const Args&...args){ print_single(t,2); print(args...); } string readString(){ string s; cin>>s; return s; } template<class T> T sq(const T& t){ return t*t; } void YES(bool ex=true){ cout<<"YES\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void NO(bool ex=true){ cout<<"NO\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void Yes(bool ex=true){ cout<<"Yes\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void No(bool ex=true){ cout<<"No\n"; if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } //#define CAPITAL /* void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif }*/ void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); #ifdef LOCAL cout.flush(); #endif } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int topbit(ull t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int botbit(ull a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } int popcount(ull t){ return __builtin_popcountll(t); } int bitparity(ll t){ return __builtin_parityll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)<<i)-1; } ull umask(int i){ return (ull(1)<<i)-1; } ll minp2(ll n){ if(n<=1)return 1; else return ll(1)<<(topbit(n-1)+1); } bool inc(int a,int b,int c){ return a<=b&&b<=c; } template<class t> void mkuni(vc<t>&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] //#ifdef LOCAL static mt19937_64 gen; /*#else static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); #endif*/ return uniform_int_distribution<ll>(l, r)(gen); } ll rand_int(ll k){ //[0,k) return rand_int(0,k-1); } template<class t> void myshuffle(vc<t>&a){ rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template<class t> int lwb(const vc<t>&v,const t&a){ return lower_bound(all(v),a)-v.bg; } template<class t> bool bis(const vc<t>&v,const t&a){ return binary_search(all(v),a); } vvc<int> readGraph(int n,int m){ vvc<int> g(n); rep(i,m){ int a,b; cin>>a>>b; //sc.read(a,b); a--;b--; g[a].pb(b); g[b].pb(a); } return g; } vvc<int> readTree(int n){ return readGraph(n,n-1); } template<class t> vc<t> presum(const vc<t>&a){ vc<t> s(si(a)+1); rep(i,si(a))s[i+1]=s[i]+a[i]; return s; } vc<ll> presum(const vi&a){ vc<ll> s(si(a)+1); rep(i,si(a))s[i+1]=s[i]+a[i]; return s; } //BIT で数列を管理するときに使う (CF850C) template<class t> vc<t> predif(vc<t> a){ gnr(i,1,si(a))a[i]-=a[i-1]; return a; } template<class t> vvc<ll> imos(const vvc<t>&a){ int n=si(a),m=si(a[0]); vvc<ll> b(n+1,vc<ll>(m+1)); rep(i,n)rep(j,m) b[i+1][j+1]=b[i+1][j]+b[i][j+1]-b[i][j]+a[i][j]; return b; } //verify してないや void transvvc(int&n,int&m){ swap(n,m); } template<class t,class... Args> void transvvc(int&n,int&m,vvc<t>&a,Args&...args){ assert(si(a)==n); vvc<t> b(m,vi(n)); rep(i,n){ assert(si(a[i])==m); rep(j,m)b[j][i]=a[i][j]; } a.swap(b); transvvc(n,m,args...); } //CF854E void rotvvc(int&n,int&m){ swap(n,m); } template<class t,class... Args> void rotvvc(int&n,int&m,vvc<t>&a,Args&...args){ assert(si(a)==n); vvc<t> b(m,vi(n)); rep(i,n){ assert(si(a[i])==m); rep(j,m)b[m-1-j][i]=a[i][j]; } a.swap(b); rotvvc(n,m,args...); } //ソートして i 番目が idx[i] //CF850C template<class t> vi sortidx(const vc<t>&a){ int n=si(a); vi idx(n);iota(all(idx),0); sort(all(idx),[&](int i,int j){return a[i]<a[j];}); return idx; } //vs[i]=a[idx[i]] //例えば sortidx で得た idx を使えば単にソート列になって返ってくる //CF850C template<class t> vc<t> a_idx(const vc<t>&a,const vi&idx){ int n=si(a); assert(si(idx)==n); vc<t> vs(n); rep(i,n)vs[i]=a[idx[i]]; return vs; } //CF850C vi invperm(const vi&p){ int n=si(p); vi q(n); rep(i,n)q[p[i]]=i; return q; } template<class t,class s=t> s SUM(const vc<t>&a){ return accumulate(all(a),s(0)); } template<class t> t MAX(const vc<t>&a){ return *max_element(all(a)); } template<class t> pair<t,int> MAXi(const vc<t>&a){ auto itr=max_element(all(a)); return mp(*itr,itr-a.bg); } template<class t> t MIN(const vc<t>&a){ return *min_element(all(a)); } template<class t> pair<t,int> MINi(const vc<t>&a){ auto itr=min_element(all(a)); return mp(*itr,itr-a.bg); } vi vid(int n){ vi res(n);iota(all(res),0); return res; } template<class S> void soin(S&s){ sort(all(s)); } template<class S> S soout(S s){ soin(s); return s; } template<class S> void rein(S&s){ reverse(all(s)); } template<class S> S reout(S s){ rein(s); return s; } template<class t,class u> pair<t,u>&operator+=(pair<t,u>&a,pair<t,u> b){ a.a+=b.a;a.b+=b.b;return a;} template<class t,class u> pair<t,u>&operator-=(pair<t,u>&a,pair<t,u> b){ a.a-=b.a;a.b-=b.b;return a;} template<class t,class u> pair<t,u> operator+(pair<t,u> a,pair<t,u> b){return mp(a.a+b.a,a.b+b.b);} template<class t,class u> pair<t,u> operator-(pair<t,u> a,pair<t,u> b){return mp(a.a-b.a,a.b-b.b);} template<class t> t gpp(vc<t>&vs){ assert(si(vs)); t res=move(vs.back()); vs.pop_back(); return res; } template<class t> void pb(vc<t>&a,const vc<t>&b){ a.insert(a.ed,all(b)); } template<class t> vc<t> cat(vc<t> a,const vc<t>&b){ pb(a,b); return a; } template<class t,class u> vc<t>& operator+=(vc<t>&a,u x){ for(auto&v:a)v+=x; return a; } template<class t,class u> vc<t> operator+(vc<t> a,u x){ return a+=x; } template<class t,class u> vc<t>& operator-=(vc<t>&a,u x){ for(auto&v:a)v-=x; return a; } template<class t,class u> vc<t>& operator-(vc<t> a,u x){ return a-=x; } //CCPC Finals 2021 H //Multiuni2023-3 E struct dominator_tree{ int n; vvc<int> g,rG,bct; vi idom,semi,us,id,rId,par,mn,anc; dominator_tree(int nn):n(nn), g(n),rG(n),bct(n), idom(n,-1),semi(n),us(n),id(n,-1),rId(n),par(n,-1),mn(n),anc(n,-1){ iota(all(semi),0); iota(all(mn),0); } void ae(int a,int b){ if(a==b)return; g[a].pb(b); rG[b].pb(a); } int find(int v){ if(anc[v]==-1) return v; int a=find(anc[v]); if(id[semi[mn[anc[v]]]]<id[semi[mn[v]]]) mn[v]=mn[anc[v]]; return anc[v]=a; } void link(int c,int p){ anc[c]=p; } void dfs(int v,int p,int& i){ if(id[v]!=-1) return; id[v]=i; rId[i++]=v; par[v]=p; for(int c:g[v]) dfs(c,v,i); } //return idom or -1 if unreachable from the root vi calc(int root){ int sz=0; dfs(root,-1,sz); for(int i=sz-1;i>0;i--){ int w=rId[i]; for(int v:rG[w])if(id[v]!=-1){ find(v); if(id[semi[mn[v]]]<id[semi[w]]) semi[w]=semi[mn[v]]; } bct[semi[w]].pb(w); for(int v:bct[par[w]]){ find(v); us[v]=mn[v]; } bct[par[w]].clear(); link(w,par[w]); } rng(i,1,sz){ int w=rId[i]; if(semi[w]==semi[us[w]]) idom[w]=semi[w]; else idom[w]=idom[us[w]]; } return idom; } }; //dep,par は not verified //yukicoder no.1024 //https://www.codechef.com/LTIME110A/problems/TREEQUER //IOI2022 Islands template<class E> struct treedfs{ const vvc<E>&g; const int n; int cnt; vi par,dep,in,out,ni; void dfs(int v,int p,int d){ par[v]=p; dep[v]=d; in[v]=cnt++; for(auto e:g[v])if(e!=p) dfs(e,v,d+1); out[v]=cnt; } treedfs(const vvc<E>&gg,int r):g(gg),n(si(g)),cnt(0),par(n),dep(n,-1),in(n,-1),out(n,-1){ dfs(r,-1,0); //not necessarily connected ni.resize(cnt); rep(i,n)if(in[i]!=-1)ni[in[i]]=i; } bool asde(int a,int b){ return in[a]<=in[b]&&out[b]<=out[a]; } }; bool dbg=false; struct E{ int to,id; operator int()const{return to;} }; std::variant<bool, std::vector<int>> find_journey( int n, int m, std::vector<int> U, std::vector<int> V) { vvc<E> g(n); rep(i,m)g[U[i]].pb({V[i],i}); int twocyc[2]{-1,-1}; vi pv(n,-1),pe(n,-1),dep(n,-1),bw(n,-1),arc; { vi ls; auto dfs=[&](auto self,int v,int p,int e,int d)->void{ assert(dep[v]==-1); ls.pb(v); pv[v]=p; pe[v]=e; dep[v]=d; int x[2]{-1,-1}; for(auto [to,id]:g[v]){ if(dep[to]==-1){ self(self,to,v,id,d+1); int y=bw[to]; rep(k,2)if(x[k]<y)swap(x[k],y); }else if(dep[to]<dep[v]){ bw[ls[dep[to]+1]]=id; arc.pb(id); }else{ //do nothing } } ls.pop_back(); rep(k,2)chmax(bw[v],x[k]); if(x[0]!=-1&&x[1]!=-1){ rep(k,2)twocyc[k]=x[k]; } }; dfs(dfs,0,-1,-1,0); } if(twocyc[0]!=-1&&twocyc[1]!=-1){ return true; } /* rep(phase,2){ vi in(n,-1); int head=0; auto dfs=[&](auto self,int v){ in[v]=head++; for(auto ch:t[v])self(self,ch); }; int mn=inf,mx=-inf; tuple<int,int,int> x,y; for(auto [id,v,pre]:bw){ if(chmin(mn,in[v]))x=mt(id,v,pre); if(chmax(mx,in[pre]))y=mt(id,v,pre); } if(mn<mx){ } rep(i,n)rein(t[i]); }*/ dominator_tree dt(n); rep(i,m)dt.ae(U[i],V[i]); vi idom=dt.calc(0); vvc<int> t(n); rep(i,n)if(idom[i]!=-1)t[idom[i]].pb(i); treedfs<int> w(t,0); int singlecyc=-1; vc<bool> uni(n,true); for(auto i:w.ni){ if(w.par[i]!=-1){ uni[i]=uni[w.par[i]]; if(w.par[i]!=pv[i]) uni[i]=false; } } for(auto i:arc){ if(!w.asde(V[i],U[i]))singlecyc=i; if(!uni[V[i]])singlecyc=i; } if(singlecyc==-1){ return false; } return true; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...