UVa : 4201 (Switch Bulbs)


// http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4201

// CPU Time : 3.182s
// memory : 1388 kbytes

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <bitset>
#include <utility>
#include <set>
#include <math.h>
#define pi acos(-1.0)
#define N 1000000
using namespace std;

map <int, int> visited;
int n, m;

void reset ()
{
    for ( int i = 1; i < (1 << n); i++ ) {
        visited [i] = -1;
    }

    visited [0] = 0;
}

int main ()
{
    int testCase;
    scanf ("%d", &testCase);
    int cases = 0;

    while ( testCase-- ) {
        scanf ("%d %d", &n, &m);

        visited.clear ();
        vector <int> switchs;

        for ( int i = 0; i < m; i++ ) {
            int nums; scanf ("%d", &nums);
            int total = 0;
            for ( int j = 0; j < nums; j++ ) {
                int bulb; scanf ("%d", &bulb);
                total |= (1 << bulb);
            }
            switchs.push_back (total);
        }

        reset ();

        queue <int> q;
        q.push (0);

        while ( !q.empty () ) {
            int p = q.front ();
            q.pop ();

            for ( int j = 0; j < m; j++ ) {
                int ns = p ^ switchs [j];
                if ( visited [ns] == -1 ) {
                    visited [ns] = visited [p] + 1;
                    q.push (ns);
                }
            }
        }

        int query;
        scanf ("%d", &query);

        printf ("Case %d:\n", ++cases);

        for (int i = 0; i < query; i++ ) {
            char q [30]; scanf ("%s", q);
            long int p = strtol (q, NULL, 2);
            printf ("%d\n", visited [p]);
        }

        printf ("\n");
    }

    return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s