【HDU】2828 Lamp
1 #include<cstdio>2 #include<cstring>
3 #define MAXN 500010
4 #define MAXM 1010
5 #define INF 0x7FFFFFFF
6 int L, R, U, D;
7 int H, C, S, X;
8 bool vis;
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;
19 U = D = i;
20 S = 0;
21 }
22 R = 0;
23 size = n + 1;
24 }
25 inline void Link(int r, int c)
26 {
27 D = D;
28 U = c;
29 U] = size;
30 D = size;
31 if (H < 0)
32 H = L = R = size;
33 else
34 {
35 L = H;
36 R = R];
37 L]] = size;
38 R] = size;
39 }
40 S++;
41 X = r;
42 C = c;
43 }
44 void Remove(int c)
45 {
46 int i;
47 for (i = D; i != c; i = D)
48 {
49 R] = R;
50 L] = L;
51 }
52 }
53 void Resume(int c)
54 {
55 int i;
56 for (i = D; i != c; i = D)
57 R] = L] = i;
58 }
59 bool Dance()
60 {
61 if (R == 0)
62 return true;
63 int i, j, temp, c;
64 for (temp = INF,i = R; i; i = R)
65 {
66 if (temp > S)
67 {
68 temp = S;
69 c = i;
70 }
71 }
72 for (i = D; i != c; i = D)
73 {
74 if (vis ^ 1])
75 continue;
76 vis] = true;
77 Remove(i);
78 for (j = R; j != i; j = R)
79 Remove(j);
80 if (Dance())
81 return true;
82 for (j = L; j != i; j = L)
83 Resume(j);
84 Resume(i);
85 vis] = false;
86 }
87 return false;
88 }
89 int main()
90 {
91 char s;
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)
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 }
页:
[1]