869 - Airline Comparison

[miollnyr]

Hi,

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;
}

[Shafaet_du]

Code: Select all

5

0
0

0
2
a b
b c

4
a b
b c
d e
e f
4
a e
b c
d e
e f

4
a b
b c
D e
e F
5
e D
a b
b c
E F
a c

6
a b
a c
b e
c d
g h
h i
6
a b
b e
a c
c d
d i
g h

output from my ac code:

Code: Select all

YES

NO

NO

YES

NO

I used floyd warshall to solve this. it took .004 sec.

[Imti]

I don't understand why the cities are not case sensitive as problem description didn't cleared it.
How to get that point 'case insensitive' from this problem?

[SyFy]

this should help others

input:

Code: Select all

1

5
# $
A 0
D #
* B
@ F

3
A D
h &
0 8

output:

Code: Select all

NO

good luck!

[Scarecrow]

for other's convenience, judge I/O set doesn't contain any character other than 26 capitals letters. 'cause my AC code handled only these 26 characters.

[hquilo]

Hi,

I find the problem statement confusing or incomplete. In particular, it is not clear from the statement if the trip relation is reflexive. Also, it does not mention if N and M can be zero.

Consider the following test cases:

Code: Select all

3

0
1
a a

1
a a
0

1
a a
1
b b

In these three cases the answer should be YES if the relation is reflexive; otherwise in all cases it should be no.

As a matter of fact my AC code outputs YES for all these three test cases. However, this output is not consistent for other AC solutions I found online. Then, the judge input does not contain such test cases but, anyway, it would be nice to have a clearer problem statement (at least annotated in this forum).

Regards.

[brianfry713]

The judge's input doesn't contain any test cases where N or M equals 0 or a flight has the same origin and destination cities.

[predicate]

Code: Select all

4
a b
b c
D e
e F
5
e D
a b
b c
E F
a c

The output for this test case give above is wrong. It should be No.