Codeforces #865 : Div1 C. Between

色々考えつくなぁ。
https://codeforces.com/contest/1815/problem/C

問題

整数Nと、N以下の整数対(A[i],B[i])がM組与えられる。
以下を満たす整数列Xの最大長を求めよ。

• 1は1回しか登場できない。
• X中に2回以上A[i]が登場するとき、その間に1個以上B[i]がなければならない。

解法

M個の条件に現れない整数は、何個でもXに追加できるので、そのような整数があればその時点で解は無限大。
A[i]の個数に対しB[i]は+1個置けるので、この条件から各要素の配置できる個数が決まる。
あとは置ける整数を端から順に貪欲で置いていけばよい。

int T,N,M;
vector<int> E[1515],RE[1515];
int D[1515];
int need[1515];
int O[1515],re[1515];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		int ok=0;
		FOR(i,N+1) {
			E[i].clear();
			RE[i].clear();
			D[i]=0;
			need[i]=0;
		}
		
		FOR(i,M) {
			cin>>x>>y;
			if(x==1) {
				i--;
				M--;
				continue;
			}
			E[x-1].push_back(y-1);
			RE[y-1].push_back(x-1);
			need[x-1]++;
		}
		D[0]=1;
		queue<int> Q;
		Q.push(0);
		int step=0;
		while(Q.size()) {
			x=Q.front();
			Q.pop();
			O[x]=step;
			re[step]=x;
			step++;
			FORR(e,RE[x]) if(D[e]==0) {
				D[e]=1;
				Q.push(e);
			}
		}
		FOR(i,N) if(D[i]==0) break;
		ZERO(need);
		if(i<N) {
			cout<<"INFINITE"<<endl;
			continue;
		}
		priority_queue<int> PQ;
		vector<int> V;
		FOR(i,N) PQ.push(i);
		while(PQ.size()) {
			x=PQ.top();
			PQ.pop();
			y=re[x];
			V.push_back(y+1);
			FORR(e,RE[y]) {
				need[e]--;
				if(need[e]==0) PQ.push(O[e]);
			}
			if(y) {
				need[y]=E[y].size();
			}
		}
		cout<<"FINITE"<<endl;
		cout<<V.size()<<endl;
		FORR(v,V) cout<<v<<" ";
		cout<<endl;
		
	}
}

まとめ

本番結構苦戦してるな…。