oj.uz

Submission #83385

# Submission time Handle Problem Language Result Execution time Memory
83385 2018-11-07T13:17:44 Z luciocf Cezar (COCI16_cezar) C++14
30 / 100
 3 ms 624 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 584 KB Output is correct
2 Correct 2 ms 584 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 620 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 624 KB Output is correct
2 Correct 3 ms 624 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 624 KB Output isn't correct
2 Halted 0 ms 0 KB -