Div 1, Level 1
Div 1, Level 2
Div 1, Level 3
#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!
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!
No comments :
Post a Comment