JOI 2025/2026 二次予選 : E - ビ太郎の旅 3 (Bitaro's Travel 3)

これは割とすんなり解けた。
https://atcoder.jp/contests/joi2026yo2/tasks/joi2026_yo2_e

問題

N点M辺の無向グラフが与えられる。
このグラフ上で、以下を満たすパスのみ有効とする。

• 奇数回目の移動では、頂点番号が増える方向に移動する
• 偶数回目の移動では、頂点番号が減る方向に移動する

各頂点を始点としたとき、上記条件のもとで到達不可能な頂点の数をそれぞれ求めよ。

解法

到達可能な点を数え上げる。

パスを成す頂点をP[0],P[1],....とする。
頂点P[2k]から頂点P[2k+2]に移動可能な条件は、P[2k]とP[2k+2]それぞれから辺が張られた頂点のうち、P[2k]＜P[2k+1]、P[2k+2]＜P[2k+1]を満たすような頂点P[2k+1]が存在することである。

逆に、P[2k+1]の隣接頂点のうち、P[2k+1]未満の頂点番号の2点間は、移動可能ということになる。
よってそれらをunion-findで連結しよう。
この連結成分内の頂点を始点としたとき、連結成分及びそれらの隣接点のうち頂点番号が増加するものまで到達可能ということになる。

int N,M;
vector<int> E[303030];

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;
	}
};
UF<303030> uf;
set<int> can[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) {
		sort(ALL(E[i]));
		FOR(j,E[i].size()) if(j) {
			if(E[i][j]<i) uf(E[i][j],E[i][j-1]);
		}
	}
	FOR(i,N) {
		can[uf[i]].insert(i);
		FORR(e,E[i]) if(e>i) can[uf[i]].insert(e);
	}
	
	FOR(i,N) cout<<N-can[uf[i]].size()<<endl;
	
}

まとめ

門松列か？と思ったけど考えたら違った。