Lamp

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 855 Accepted Submission(s): 265
Special Judge

Problem Description

There are several switches and lamps in the room, however, the connections between them are very complicated. One lamp may be controlled by several switches, and one switch may controls at most two lamps. And what’s more, some connections are reversed by mistake, so it’s possible that some lamp is lighted when its corresponding switch is “OFF”!

To make things easier, we number all the lamps from 1 to N, and all the switches 1 to M. For each lamps, we give a list of switches controlling it. For example, for Lamp 1, the list is “1 ON 3 OFF 9 ON”, that means Lamp 1 will be lighted if the Switch 1 is at the “ON” state OR the Switch 3 is “OFF” OR the Switch 9 is “ON”.

Now you are requested to turn on or off the switches to make all the lamps lighted.

Input

There are several test cases in the input. The first line of each test case contains N and M (1 <= N,M <= 500), then N lines follow, each indicating one lamp. Each line begins with a number K, indicating the number of switches controlling this lamp, then K pairs of “x ON” or “x OFF” follow.

Output

Output one line for each test case, each contains M strings “ON” or “OFF”, indicating the corresponding state of the switches. For the solution may be not unique, any correct answer will be OK. If there are no solutions, output “-1” instead.

Sample Input

       2 2 2 1 ON 2 ON 1 1 OFF 2 1 1 1 ON 1 1 OFF 

Sample Output

       OFF ON -1 

Source

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int maxn=1010,maxm=510;const int maxnode=maxn*maxm;const int INF=0x3f3f3f3f;int n,m;bool flag;struct DLX{    int n,m,size;    int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];    int H[maxn],S[maxm];    int ansd,ans[maxn];    int LAMP[maxn];    bool vis[maxn];    void init(int _n,int _m)    {        n=_n; m=_m;        for(int i=0;i<=m;i++)        {            S[i]=0; U[i]=D[i]=i;            L[i]=i-1; R[i]=i+1;        }        R[m]=0; L[0]=m;        size=m;        for(int i=1;i<=n;i++)        {            vis[i]=false;            LAMP[i]=0;            H[i]=-1;        }        flag=false;    }    void Link(int r,int c)    {        ++S[Col[++size]=c];        Row[size]=r;        D[size]=D[c];        U[D[c]]=size;        U[size]=c;        D[c]=size;        if(H[r]<0) H[r]=L[size]=R[size]=size;        else        {            R[size]=R[H[r]];            L[R[H[r]]]=size;            L[size]=H[r];            R[H[r]]=size;        }    }    void remove(int c)    {        for(int i=D[c];i!=c;i=D[i])            L[R[i]]=L[i],R[L[i]]=R[i];    }    void resume(int c)    {        for(int i=U[c];i!=c;i=U[i])            L[R[i]]=R[L[i]]=i;    }    void Dance(int d)    {        if(flag) return ;        if(R[0]==0)        {            ///find ans            for(int i=0;i

转载地址：http://jdyca.baihongyu.com/

你可能感兴趣的文章

开源方案搭建可离线的精美矢量切片地图服务-5.Mapbox离线项目实现