【HDOJ】2828 Lamp

DLX简单题目。
  1 /*  */
  2 #include <iostream>
  3 #include <sstream>
  4 #include <string>
  5 #include <map>
  6 #include <queue>
  7 #include <set>
  8 #include <stack>
  9 #include <vector>
 10 #include <deque>
 11 #include <algorithm>
 12 #include <cstdio>
 13 #include <cmath>
 14 #include <ctime>
 15 #include <cstring>
 16 #include <climits>
 17 #include <cctype>
 18 #include <cassert>
 19 #include <functional>
 20 #include <iterator>
 21 #include <iomanip>
 22 using namespace std;
 23 //#pragma comment(linker,"/STACK:102400000,1024000")
 24 
 25 #define sti                set<int>
 26 #define stpii            set<pair<int, int> >
 27 #define mpii            map<int,int>
 28 #define vi                vector<int>
 29 #define pii                pair<int,int>
 30 #define vpii            vector<pair<int,int> >
 31 #define rep(i, a, n)     for (int i=a;i<n;++i)
 32 #define per(i, a, n)     for (int i=n-1;i>=a;--i)
 33 #define clr                clear
 34 #define pb                 push_back
 35 #define mp                 make_pair
 36 #define fir                first
 37 #define sec                second
 38 #define all(x)             (x).begin(),(x).end()
 39 #define SZ(x)             ((int)(x).size())
 40 #define lson            l, mid, rt<<1
 41 #define rson            mid+1, r, rt<<1|1
 42 
 43 const int INF = 0x3f3f3f3f;
 44 
 45 typedef struct {
 46     static const int maxn = 1e6+5;
 47     
 48     int L[maxn], R[maxn], U[maxn], D[maxn];
 49     int H[maxn];
 50     int row[maxn], col[maxn], S[maxn];
 51     
 52     bool visit[1205];
 53     int sz;
 54     int ans[maxn], ansd;
 55     
 56     void init(int n) {
 57         rep(i, 0, n+1) {
 58             L[i] = i - 1;
 59             R[i] = i + 1;
 60             U[i] = i;
 61             D[i] = i;
 62             col[i] = i;
 63         }
 64         
 65         memset(S, 0, sizeof(S));
 66         memset(visit, false, sizeof(visit));
 67         memset(H, -1, sizeof(H));
 68         R[n] = 0;
 69         L[0] = n;
 70         sz = n + 1;
 71     }
 72     
 73     void link(int r, int c) {
 74         U[sz] = c;
 75         D[sz] = D[c];
 76         U[D[c]] = sz;
 77         D[c] = sz;
 78         if (H[r] < 0) {
 79             H[r] = L[sz] = R[sz] = sz;
 80         } else {
 81             L[sz] = H[r];
 82             R[sz] = R[H[r]];
 83             L[R[H[r]]] = sz;
 84             R[H[r]] = sz;
 85         }
 86         
 87         ++S[c];
 88         col[sz] = c;
 89         row[sz] = r;
 90         ++sz;
 91     }
 92     
 93     void remove(int c)  {
 94         L[R[c]] = L[c];
 95         R[L[c]] = R[c];
 96         for (int i=D[c]; i!=c; i=D[i]) {
 97             for (int j=R[i]; j!=i; j=R[j]) {
 98                 U[D[j]] = U[j];
 99                 D[U[j]] = D[j];
100                 --S[col[j]];
101             }
102         }
103     }
104     
105     void restore(int c)  {
106         L[R[c]] = c;
107         R[L[c]] = c;
108         for (int i=D[c]; i!=c; i=D[i]) {
109             for (int j=R[i]; j!=i; j=R[j]) {
110                 U[D[j]] = j;
111                 D[U[j]] = j;
112                 ++S[col[j]];
113             }
114         }
115     }
116     
117     void remove_(int c) {
118         for (int i=D[c]; i!=c; i=D[i]) {
119             L[R[i]] = L[i];
120             R[L[i]] = R[i];
121         }
122     }
123     
124     void restore_(int c) {
125         for (int i=D[c]; i!=c; i=D[i]) {
126             L[R[i]] = i;
127             R[L[i]] = i;
128         }
129     }
130     
131     bool dfs(int cur) {
132         if (!R[0]) {
133             return true;
134         }
135         
136         int c = R[0];
137         for (int i=R[0]; i!=0; i=R[i]) {
138             if (S[i] < S[c])
139                 c = i;
140         }
141         
142         for (int i=D[c]; i!=c; i=D[i]) {
143             if (visit[row[i]^1])
144                 continue;
145             visit[row[i]] = true;
146             remove_(i);
147             for (int j=R[i]; j!=i; j=R[j])
148                 remove_(j);
149             if (dfs(cur+1))    return true;
150             for (int j=L[i]; j!=i; j=L[j])
151                 restore_(j);
152             restore_(i);
153             visit[row[i]] = false;
154         }
155         
156         return false;
157     }
158     
159 } DLX;
160 
161 DLX solver;
162 
163 int main() {
164     ios::sync_with_stdio(false);
165     #ifndef ONLINE_JUDGE
166         freopen("data.in", "r", stdin);
167         freopen("data.out", "w", stdout);
168     #endif
169     
170     int n, m;
171     int ln, k;
172     char op[8];
173     bool flag;
174     
175     while (scanf("%d %d", &n, &m)!=EOF) {
176         solver.init(n);
177         rep(i, 1, n+1) {
178             scanf("%d", &ln);
179             while (ln--) {
180                 scanf("%d %s", &k, op);
181                 --k;
182                 if (op[1] == 'N') {
183                     solver.link(k<<1, i);
184                 } else {
185                     solver.link(k<<1|1, i);
186                 }
187             }
188         }
189         
190         flag = solver.dfs(0);
191         if (flag) {
192             if (solver.visit[1]) {
193                 printf("OFF");
194             } else {
195                 printf("ON");
196             }
197             m <<= 1;
198             for (int i=2; i<m; i+=2) {
199                 if (solver.visit[i]) {
200                     printf(" ON");
201                 } else {
202                     printf(" OFF");
203                 }
204             }
205             putchar('
');
206         } else {
207             puts("-1");
208         }
209     }
210     
211     #ifndef ONLINE_JUDGE
212         printf("time = %d.
", (int)clock());
213     #endif
214     
215     return 0;
216 }