【HDU】2828 Lamp

  1 #include<cstdio>
  2 #include<cstring>
  3 #define MAXN 500010
  4 #define MAXM 1010
  5 #define INF 0x7FFFFFFF
  6 int L[MAXN], R[MAXN], U[MAXN], D[MAXN];
  7 int H[MAXM], C[MAXN], S[MAXM], X[MAXN];
  8 bool vis[MAXM];
  9 int size;
 10 void Init(int n)
 11 {
 12     int i;
 13     memset(vis, false, sizeof(vis));
 14     memset(H, -1, sizeof(H));
 15     for (i = 0; i <= n; i++)
 16     {
 17         R[i] = i + 1;
 18         L[i + 1] = i;
 19         U[i] = D[i] = i;
 20         S[i] = 0;
 21     }
 22     R[n] = 0;
 23     size = n + 1;
 24 }
 25 inline void Link(int r, int c)
 26 {
 27     D[size] = D[c];
 28     U[size] = c;
 29     U[D[c]] = size;
 30     D[c] = size;
 31     if (H[r] < 0)
 32         H[r] = L[size] = R[size] = size;
 33     else
 34     {
 35         L[size] = H[r];
 36         R[size] = R[H[r]];
 37         L[R[H[r]]] = size;
 38         R[H[r]] = size;
 39     }
 40     S[c]++;
 41     X[size] = r;
 42     C[size++] = c;
 43 }
 44 void Remove(int c)
 45 {
 46     int i;
 47     for (i = D[c]; i != c; i = D[i])
 48     {
 49         R[L[i]] = R[i];
 50         L[R[i]] = L[i];
 51     }
 52 }
 53 void Resume(int c)
 54 {
 55     int i;
 56     for (i = D[c]; i != c; i = D[i])
 57         R[L[i]] = L[R[i]] = i;
 58 }
 59 bool Dance()
 60 {
 61     if (R[0] == 0)
 62         return true;
 63     int i, j, temp, c;
 64     for (temp = INF,i = R[0]; i; i = R[i])
 65     {
 66         if (temp > S[i])
 67         {
 68             temp = S[i];
 69             c = i;
 70         }
 71     }
 72     for (i = D[c]; i != c; i = D[i])
 73     {
 74         if (vis[X[i] ^ 1])
 75             continue;
 76         vis[X[i]] = true;
 77         Remove(i);
 78         for (j = R[i]; j != i; j = R[j])
 79             Remove(j);
 80         if (Dance())
 81             return true;
 82         for (j = L[i]; j != i; j = L[j])
 83             Resume(j);
 84         Resume(i);
 85         vis[X[i]] = false;
 86     }
 87     return false;
 88 }
 89 int main()
 90 {
 91     char s[10];
 92     int n, m, q, x, i;
 93     while (~scanf("%d%d", &n, &m))
 94     {
 95         Init(n);
 96         for (i = 1; i <= n; i++)
 97         {
 98             scanf("%d", &q);
 99             while (q--)
100             {
101                 scanf("%d %s", &x, s);
102                 if (strcmp(s, "ON") == 0)
103                     Link((x - 1) << 1, i);
104                 else
105                     Link((x - 1) << 1 | 1, i);
106             }
107         }
108         if (Dance())
109         {
110             if (!vis[1])
111                 printf("ON");
112             else
113                 printf("OFF");
114             for (i = 2; i < (m << 1); i += 2)
115             {
116                 if (!vis[i])
117                     printf(" OFF");
118                 else
119                     printf(" ON");
120             }
121             putchar('\n');
122         }
123         else
124             puts("-1");
125     }
126     return 0;
127 }