TCO2003 Round 02

Div 1, Level 1
Div 1, Level 2
Div 1, Level 3

Tutorials:

Division One - Level Three:

Solution

Source Code:

Division One - Level Two:

Solution

Using dfs to find all possible elements for one set of two classes.

Source Code:

//Fri Jun 10 01:27:14 CDT 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

class Marketing {
public:
    long long howMany(vector <string>);
    bool dfs(int x, int);
    bool grid[31][31];
    int type[31];
    int N;
};

bool Marketing::dfs(int x, int b){
    if(type[x] >= 0) return type[x] == b;
    type[x] = b;
    for(int i=0; i<N; i++){
        if(grid[x][i] && dfs(i, 1-b)==false)
            return false;
    }
    return true;
}

long long Marketing::howMany(vector <string> compete) {
    memset(grid, false, sizeof(grid));
    memset(type, -1, sizeof(type));
    N = compete.size();
    for(int i=0; i<N; i++){
        stringstream s(compete[i]);
        int num;
        while(s >> num){
            grid[i][num] = true;
            grid[num][i] = true;
        }
    }
    long long ret = 1LL;
    for(int i=0; i<N; i++){
        if(type[i] < 0){
//          type[i] = 0;
            ret <<= 1;
            if(dfs(i, 0)==false) return -1;
        }
    }
    return ret;
}

//<%:testing-code%>
//Powered by [KawigiEdit] 2.0!

Division One - Level One:

Solution

Source Code: