2150.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2150 on 2006-04-21 at 22:11:36 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int LM = 102400;
const int INF = 1 << 30;

class Line {
public:
	char type;
	int arg[2], nxt[2], in;
	int o, best, id;
	int make(int);
};
int Line::make(int co) {
	o = co; in = id= 0; best = -INF;
	char line[84], t[6];
	if(gets(line) == NULL) return -1;
	else if(line[0] == 0) return 0;
	sscanf(line, "%s %d %d", t, &arg[0], &arg[1]); type = t[0];
	if(type == 'd') return 1;
	else if(type != 'j') nxt[in++] = o+1;
	else nxt[in++] = arg[0]-1;
	if(type == 'i' && arg[0]-1 != o+1) nxt[in++] = arg[0]-1;
	return 1;
}

Line tpl[LM];

int main()
{
	int ln, stack[LM], i, best;
	bool vst[LM], end = false;

	while(!end) {
		for(ln = 0; true; ln++) {
			int r = tpl[ln].make(ln);
			if(r == -1) end = true;
			if(r != 1) break;
		}
		int vn = 1, top = 0; stack[top++] = 0;
		memset(vst, false, sizeof(vst)); vst[0] = true;
		while(top > 0) {
			int p = stack[--top];
			for(i = 0; i < tpl[p].in; i++) {
				int o = tpl[p].nxt[i]; tpl[o].id++;
				if(!vst[o]) { vst[o] = true; stack[top++] = o; vn++; }
			}
		}
		int pn = 0; top = 0;
		if(tpl[0].id == 0) { stack[top++] = 0; pn++; }
		tpl[0].best = 0; best = -INF;
		while(top > 0) {
			int p = stack[--top]; tpl[p].best++;
			switch(tpl[p].type) {
			case 'd': best = max(best, tpl[p].best); break;
			case 'l': tpl[p].best += (tpl[p].best-tpl[tpl[p].arg[0]-1].best+1) * (tpl[p].arg[1]-1); break;
			}
			for(i = 0; i < tpl[p].in; i++) {
				int o = tpl[p].nxt[i];
				if(o >= ln) break;
				tpl[o].best = max(tpl[o].best, tpl[p].best);
				if(--tpl[o].id == 0) { stack[top++] = o; pn++; }
			}
		}
		if(pn == vn && best > 0) printf("%d\n", best);
		else printf("infinity\n");
	}
}