oj.uz

Submission #91146

# Submission time Handle Problem Language Result Execution time Memory
91146 2018-12-26T11:27:59 Z nikolapesic2802 Cezar (COCI16_cezar) C++14
70 / 100
 2 ms 1012 KB 
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;

char ans[100];
int n;
string s[120];
vector<int> eds[100];
int p[120];
int was[120];
vector<int> vv;

void dfs1(int v) {
	was[v] = 1;
	for (int u: eds[v]) {
		if (!was[u])
			dfs1(u);
		else if (was[u] == 1) {
			cout << "NE\n";
			exit(0);
		}
	}
	vv.push_back(v);
	was[v] = 2;
}



int main() {
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> s[i];
	for (int i = 0; i < n; ++i)
		cin >> p[i], --p[i];
	for (int i = 0; i < n - 1; ++i) {
		int kk = min(s[p[i]].size(), s[p[i + 1]].size());
		for (int j = 0; j < kk; ++j) {
			if (s[p[i]][j] != s[p[i + 1]][j]) {
				kk = j;
				break;
			}
		}
		if (kk == (int)s[p[i + 1]].size()) {
			cout << "NE\n";
			return 0;
		}
		if (kk == (int)s[p[i]].size())
			continue;
		eds[s[p[i + 1]][kk] - 'a'].push_back(s[p[i]][kk] - 'a');
	}
	for (int i = 0; i < 26; ++i)
		if (!was[i])
			dfs1(i);
	for (int i = 0; i < (int)vv.size(); ++i) {
		ans[vv[i]] = 'a' + i;
	}
	printf("DA\n");
	printf("%s\n", ans);
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 988 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 988 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 1012 KB Output isn't correct
2 Halted 0 ms 0 KB -