I got WA on this problem, although I have solved similar problems on this site.
Could anybody explain whats wrong with my code and / or provide some inputs / outputs?
Thanks in advance!
Code: Select all
#include <iostream>
#include <map>
#include <vector>
#include <list>
using namespace std;
typedef vector<bool> line;
typedef vector<line> matrix;
typedef pair<char,char> pcc;
typedef list<pcc> lpcc;
map<char, int> c2i;
map<int, char> i2c;
lpcc roads;
int cities = 0;
matrix E;
#ifdef WIN32
ostream& operator<<(ostream& out, const line& in)
{
int i;
for(i = 0; i < in.size(); ++i)
{
out << (in[i] ? 1 : 0);
}
return out;
}
ostream& operator<<(ostream& out, const matrix& in)
{
int i;
out << " ";
for(i = 0; i < cities; ++i)
{
out << i2c[i];
}
out << '\n';
for(i = 0; i < cities; ++i)
{
out << i2c[i] << in[i] << '\n';
}
return out;
}
#endif
line& operator+=(line& lhs, const line& rhs)
{
int i;
for(i = 0; i < lhs.size(); ++i)
{
lhs[i] = (lhs[i] || rhs[i]);
}
return lhs;
}
line& operator-=(line& lhs, const line& rhs)
{
int i;
for(i = 0; i < lhs.size(); ++i)
{
lhs[i] = (lhs[i] && !rhs[i]);
}
return lhs;
}
bool operator==(const matrix& lhs, const matrix& rhs)
{
int i, j;
for(i = 0; i < lhs.size(); ++i)
{
for(j = 0; j < lhs[i].size(); ++j)
{
if(lhs[i][j] != rhs[i][j])
{
return false;
}
}
}
return true;
}
void addCity(const char c)
{
if(c2i.find(c) == c2i.end())
{
c2i[c] = cities;
i2c[cities] = c;
++cities;
}
}
void readFirstMatrix(matrix& in)
{
int n, i;
char a, b;
cin >> n;
for(i = 0; i < n; ++i)
{
cin >> a >> b;
addCity(a);
addCity(b);
roads.push_back( pcc(a, b));
}
n = cities;
in.resize(n);
for(i = 0; i < n; ++i)
{
in[i] = line(n, false);
}
for(lpcc::iterator it = roads.begin(); it != roads.end(); ++it)
{
a = it->first;
b = it->second;
in[ c2i[a] ][ c2i[b] ] = true;
}
}
bool readSecondMatrix(matrix& in)
{
int n, i, size = cities;
char a, b;
cin >> n;
in.resize(cities);
for(i = 0; i < cities; ++i)
{
in[i] = line(cities, false);
}
for(i = 0; i < n; ++i)
{
cin >> a >> b;
if(c2i.find(a) == c2i.end() || c2i.find(b) == c2i.end())
{
return false;
}
in[ c2i[a] ][ c2i[b] ] = true;
}
return true;
}
void closure(matrix& in)
{
matrix tmp(E);
int i, j, size = in.size();
for(i = 0; i < size; ++i)
{
for(j = 0; j < size; ++j)
{
if(i != j && tmp[i][j] && in[i][j])
{
in[i] += in[j];
tmp[i][j] = false;
if(i > j)
{
tmp[i] -= in[j];
}
--i; break;
}
}
}
}
void createE(const int size)
{
int i;
E.resize(size);
for(i = 0; i < size; ++i)
{
E[i] = line(size, true);
}
}
int main()
{
int num;
cin >> num;
while(num--)
{
matrix matrix1, matrix2;
c2i.clear();
i2c.clear();
roads.clear();
cities = 0;
readFirstMatrix(matrix1);
if(readSecondMatrix(matrix2))
{
createE(matrix1.size());
closure(matrix1);
closure(matrix2);
//cout << matrix1 << "\n\n" << matrix2 << "\n\n";///
cout << (matrix1 == matrix2 ? "YES" : "NO") << (num == 0 ? "" : "\n\n");
}
else
{
cout << "NO" << (num == 0 ? "" : "\n\n");
}
}
return 0;
}