【HDU】2828 Lamp

疯狂小鸡/ty

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 + 1;
18         L[i + 1] = i;
19         U = D = i;
20         S = 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)
48     {
49         R[L] = R;
50         L[R] = L;
51     }
52 }
53 void Resume(int c)
54 {
55     int i;
56     for (i = D[c]; i != c; i = D)
57         R[L] = L[R] = 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)
65     {
66         if (temp > S)
67         {
68             temp = S;
69             c = i;
70         }
71     }
72     for (i = D[c]; i != c; i = D)
73     {
74         if (vis[X ^ 1])
75             continue;
76         vis[X] = true;
77         Remove(i);
78         for (j = R; j != i; j = R[j])
79             Remove(j);
80         if (Dance())
81             return true;
82         for (j = L; j != i; j = L[j])
83             Resume(j);
84         Resume(i);
85         vis[X] = 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)
117                     printf(" OFF");
118                 else
119                     printf(" ON");
120             }
121             putchar('\n');
122         }
123         else
124             puts("-1");
125     }
126     return 0;
127 }