Submission #83385

#	Time	Username	Problem	Language	Result	Execution time	Memory
83385		luciocf	Cezar (COCI16_cezar)	C++14	30 / 100	3 ms	624 KiB

cezar

#include <bits/stdc++.h>

using namespace std;

const int maxs = 30;

const int maxn = 110;

typedef pair<int, string> pii;

int grau[maxs], ans[maxs];

pii num[maxn];

vector<int> grafo[maxs];

string s[maxn];

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(0);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> num[i].second;

	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;

		num[x].first = i;
	}

	sort(num+1, num+n+1);

	bool ok = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = i+1; j <= n; j++)
		{
			string s1 = num[i].second, s2 = num[j].second;
			bool prefixo = 1;

			for (int k = 0; k < min(s1.size(), s2.size()); k++)
			{
				if (s1[k] == s2[k]) continue;

				grafo[s1[k]-'a'].push_back(s2[k]-'a');
				grau[s2[k]-'a']++, prefixo = 0;

				break;
			}

			if (prefixo && s1.size() > s2.size()) ok = 0;
		}
	}

	if (!ok)
	{
		cout << "NE\n";
		return 0;
	}

	queue<int> fila;
	for (int i = 0; i < 26; i++)
		if (!grau[i])
			fila.push(i);

	int atual = 0, vis = 0;
	while (!fila.empty())
	{
		int x = fila.front();
		fila.pop();

		ans[x] = atual++, vis++;

		for (auto v: grafo[x])
		{
			grau[v]--;
			if (!grau[v]) fila.push(v);
		}
	}

	if (vis != 26)
	{
		cout << "NE\n";
		return 0;
	}
	
	cout << "DA\n";
	for (int i = 0; i < 26; i++)
		cout << (char) (ans[i]+'a');
	cout << "\n";
}

Compilation message (stderr)

cezar.cpp: In function 'int main()':
cezar.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < min(s1.size(), s2.size()); k++)
                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10