3052962_ac_312ms_8860k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

struct node
{
	int st, ed;
	int room[10];
}events[13];

vector <int> f[10001], tf;
vector <int> ::iterator iter;

int flag, used[260];

bool fail;
int r;
int num[100] = {1,2,4,8,16,32,64,128,256};

void solve(int t)
{
	int i, j, k, l, tmp, tt;

	tf = f[t-1];
	for(i = 0; !fail&&i < r; i++)
	{
		if(events[i].st==t)
		{
			fail = true;
			flag++;
			l = tf.size();
			for(k = 0; k < l; k++)
			{
				tmp = tf[k];
				for(j = 1; j <= events[i].room[0]; j++)
				{
					tt = tmp&num[events[i].room[j]];
					if(tt!=0)
					{
						fail = false;
						tt = tmp&(255-num[events[i].room[j]]);
						if(used[tt]!=flag)
						{
							used[tt] = flag;
							f[t].push_back(tt);
						}
					}
				}
			}
			tf = f[t];
			f[t].clear();
		}
	}
	f[t] = tf;
	flag++;
	if(fail)
	{
		return ;
	}
	tf.clear();
	for(j = 0; j < r; j++)
	{
		if(events[j].ed==t)
		{
			for(k = 1; k <= events[j].room[0]; k++)
			{
				for(i = 0; !fail&&i < f[t].size(); i++)
				{
					tt = f[t][i]&num[events[j].room[k]];
					if(tt==0)
					{
						tt = f[t][i]|num[events[j].room[k]];
						if(used[tt]!=flag)
						{
							used[tt] = flag;
							tf.push_back(tt);
						}
					}
				}
			}
		}
	}
	for(j = 0; j < f[t].size(); j++)
	{
		if(used[f[t][j]]!=flag)
		{
			used[f[t][j]] = flag;
			tf.push_back(f[t][j]);
		}
	}
	f[t] = tf;
}

int main()
{
	int cas, i, j;
	int st, ed;
	int min, max;

	scanf("%d",&cas);
	flag = 0;
	memset(used,0,sizeof(used));
	while(cas!=0)
	{
		fail = false;
		min = 1000000;
		max = -1;
		cas--;
		scanf("%d",&r);
		for(i = 0; i < r; i++)
		{
			scanf("%d%d",&st,&ed);
			if(st < min)
			{
				min = st;
			}
			if(st > max)
			{
				max = st;
			}
			events[i].st = st;
			events[i].ed = ed;
			scanf("%d",&events[i].room[0]);
			for(j = 1; j <= events[i].room[0]; j++)
			{
				scanf("%d",&events[i].room[j]);
				events[i].room[j]--;
			}
		}
		f[min-1].clear();
		f[min-1].push_back(255);
		for(i = min; !fail&&i <= max; i++)
		{
			f[i].clear();
			solve(i);
		}
		puts(fail?"NO":"YES");
	}
	return 0;
}