MemSQL start[c]up Round 1 : C. Monsters and Diamonds

地味に面倒くさくて苦労した問題。周りにも意外と正解していない。
http://codeforces.com/contest/325/problem/C

問題

N体のモンスターがいる。
各モンスターにはルールがあり、分裂するといくつかのダイヤモンドとモンスターにわかれる。
ルールは1体あたり複数ある場合もある。

各モンスター1体から全モンスターを消すまでルール適用を繰り返した場合に、取得可能な最小・最大ダイヤモンド数を答えよ。
この際、無限にダイヤモンドを生成できる場合や、モンスターを消しきれないならそれも答えよ。

解法

まず、ダイヤモンドの最少数から求めていく。
モンスターを生成しないルールがある場合、そのモンスターの仮最小数をそのルール中のダイヤモンド数にできる。
最少数が未確定なモンスターは、仮に巨大数を割り当てておく。

後は仮最少数が小さいモンスターに対し、他のモンスターにおけるそのモンスターを含むルールを適用し、最少値を更新していけばよい。
最少値が更新されなくなったら終了。

もし最悪ループしてしまう場合(自分自身から自分自身を生成できてしまう場合)、得られるダイヤモンド数が仮の巨大数よりも大きくなるのですぐわかる。
よって、最少数が仮の巨大数のままのものは、モンスターを消しきれない。

次に最大値を考える。
ここで、最小値で無限ループするモンスターを含むルールは、モンスターを消しきれなくなるのでそのルールを削除する。

後は最少値とは逆に数が大きい順に更新していく。
途中ループするモンスターがある場合、1ループで1個以上のダイヤモンドが生成できるなら、そのループを繰り返すとダイヤがいくらでも増えるので、最大値は無限となる。

int N,M;
vector<int> PR[100001];
int D[100001];
vector<int> L[100001];
set<int> SS[100001];
set<pair<int,int> > rev[100001];
ll MI[100001],MA[100001];
int fix[100001];

ll dfs(int cur) {
	
	if(MA[cur]!=-3) return MA[cur];
	MA[cur]=-1;
	
	ll ma=0;
	int i,j,h1p=0,nh1=0;
	FOR(i,PR[cur].size()) {
		int t=PR[cur][i];
		ll tm=D[t];
		int h2=0,h1=0;
		FOR(j,L[t].size()) {
			if(L[t][j]==-1) continue;
			ll r=dfs(L[t][j]);
			if(r==-2) return MA[cur]=-2;
			if(r==-1) h1++;
			else tm+=r;
		}
		
		if(h1&&tm) return MA[cur]=-2;
		ma=max(ma,min(314000000LL,tm));
	}
	
	return MA[cur]=ma;
}

void solve() {
	int r,i,j,k,l,x,y,tx,ty;
	
	cin>>M>>N;
	FOR(i,N) MI[i]=1LL<<40;
	FOR(i,M) {
		cin>>x>>y;
		x--;
		PR[x].push_back(i);
		FOR(j,y) {
			cin>>l;
			if(l<0) D[i]++;
			else {
				L[i].push_back(l-1);
				SS[i].insert(l-1);
				rev[l-1].insert(make_pair(x,i));
			}
		}
		if(D[i]==y && D[i]<MI[x]) MI[x]=D[i];
	}
	
	set<pair<ll,int> > Q;
	FOR(i,N) if(MI[i]<1LL<<40) Q.insert(make_pair(MI[i],i));
	while(!Q.empty()) {
		pair<ll,int> p=*Q.begin();
		Q.erase(p);
		fix[p.second]=1;
		
		ITR(it,rev[p.second]) {
			if(fix[it->first]) continue;
			SS[it->second].erase(p.second);
			if(!SS[it->second].empty()) continue;
			ll tm=D[it->second];
			FOR(x,L[it->second].size()) {
				tm+=MI[L[it->second][x]];
				if(tm>=MI[it->first]) break;
			}
			if(tm>314000000 && tm<1LL<<40) tm=314000000;
			if(tm<MI[it->first]) {
				Q.erase(make_pair(MI[it->first],it->first));
				MI[it->first]=tm;
				Q.insert(make_pair(MI[it->first],it->first));
			}
		}
	}
	
	FOR(i,N) if(MI[i]==1LL<<40) MI[i]=-1;
	// rem bad
	FOR(i,N) FOR(x,PR[i].size()) {
		int t=PR[i][x];
		FOR(j,L[t].size()) if(L[t][j]!=i && MI[L[t][j]]==-1) {
			PR[i][x]=-1;
			break;
		}
	}
	
	FOR(i,N) MA[i]=(MI[i]==-1)?-1:-3;
	FOR(i,N) if(MA[i]==-3) dfs(i);
	
	FOR(i,N) _P("%lld %lld\n",MI[i],MA[i]);
}

まとめ

問題設定の割にややこしい問題。
無限ループが話をややこしくしているな。