これでグラフに持ち込もうとは考えなかったな…。
https://atcoder.jp/contests/arc165/tasks/arc165_d
問題
長さNの整数列Xを考える。
以下のM個の条件を満たすXは存在するか。
- 部分列X[A[i],B[i]]はX[C[i],D[i]]より辞書順で小さい
解法
A[i]=C[i]の場合は自明なので、そのような条件は先に取り除く。
N頂点のグラフを考える。
X[A[i]]≦X[C[i]]でなければいけないので、A[i]→C[i]に辺を張る。
このグラフに閉路がなければ、これらは条件を満たすX[*]を定められるので、問題ない。
閉路がある場合、X[A[i]]=X[C[i]]でなければならない。
それらを縮約して、A[i]+1→C[i]+1に辺を張ることを繰り返そう。
int N,M; int A[2020],B[2020],C[2020],D[2020]; vector<int> X[2020]; vector<int> Y[2020]; class SCC { public: static const int MV = 2020; vector<vector<int> > SC; int NV,GR[MV]; private: vector<int> E[MV], RE[MV], NUM; int vis[MV]; public: void init(int NV) { this->NV=NV; for(int i=0;i<NV;i++) { E[i].clear(); RE[i].clear();}} void add_edge(int x,int y) { E[x].push_back(y); RE[y].push_back(x); } void dfs(int cu) { vis[cu]=1; for(int i=0;i<E[cu].size();i++) if(!vis[E[cu][i]]) dfs(E[cu][i]); NUM.push_back(cu); } void revdfs(int cu, int ind) { int i; vis[cu]=1; GR[cu]=ind; SC[ind].push_back(cu); FOR(i,RE[cu].size()) if(!vis[RE[cu][i]]) revdfs(RE[cu][i],ind);} void scc() { int c=0,i; SC.clear(); SC.resize(NV); NUM.clear(); assert(NV); FOR(i,NV) vis[i]=0; FOR(i,NV) if(!vis[i]) dfs(i); FOR(i,NV) vis[i]=0; for(int i=NUM.size()-1;i>=0;i--) if(!vis[NUM[i]]){ SC[c].clear(); revdfs(NUM[i],c); sort(SC[c].begin(),SC[c].end()); c++; } SC.resize(c); } }; SCC scc; template<int um> class UF { public: vector<int> par,rank,cnt,G[um]; UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;} void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int count(int x) { return cnt[operator[](x)];} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; cnt[y]=cnt[x]=cnt[x]+cnt[y]; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } void dump(int num=um) { //グループ分けした配列を作る int i; FOR(i,num) G[i].clear(); FOR(i,num) G[operator[](i)].push_back(i); } }; UF<2020> uf; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>A[i]>>B[i]>>C[i]>>D[i]; A[i]--,C[i]--; if(A[i]==C[i]) { if(B[i]>=D[i]) { cout<<"No"<<endl; return; } i--; M--; continue; } for(j=A[i];j<B[i];j++) X[i].push_back(j); for(j=C[i];j<D[i];j++) Y[i].push_back(j); reverse(ALL(X[i])); reverse(ALL(Y[i])); } int num=N; while(1) { scc.init(N); FOR(i,M) { while(X[i].size()&&Y[i].size()&&uf[X[i].back()]==uf[Y[i].back()]) { X[i].pop_back(); Y[i].pop_back(); } if(Y[i].empty()) { cout<<"No"<<endl; return; } if(X[i].size()&&Y[i].size()) { scc.add_edge(uf[X[i].back()],uf[Y[i].back()]); } } scc.scc(); if(scc.SC.size()==N) break; FORR(sc,scc.SC) { num-=sc.size()-1; FORR(a,sc) uf(a,sc[0]); } } cout<<"Yes"<<endl; }
まとめ
うーむ、これ700ptか…。