///////////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define FILE_IO(x) freopen((string(x) + ".in").c_str(), "r", stdin); freopen((string(x) + ".out").c_str(), "w", stdout)
#define f first
#define s second
#define x1 x1qwer
#define y1 y1qwer
#define right right123
#define left left123
#define foreach(it, v) for (auto it : v)
#define rep(it, n) for (int it = 0; it < n; ++it)
#define forin(it, l, r) for (int it = l; it < r; ++it)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double DINF = numeric_limits<double>::infinity();
const ll MOD = 1e9 + 7;
const double EPS = 1e-7;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
mt19937 mmtw_(MOD);
uniform_int_distribution<ll> rd_;
ll randomll() { return rd_(mmtw_);}
ll rnd(ll x, ll y) { return rd_(mmtw_) % (y - x + 1) + x; }
template <class T> T fact(T n) { if (n == 1) return 1; return n * fact(n - 1); }
////////////////////////////////////////////////////////////////////////////////////////////////
const int MAXN = 105;
int n;
string s[MAXN];
int last = 1;
int to[MAXN * MAXN][26];
int mn[MAXN * MAXN];
int mx[MAXN * MAXN];
int sz[MAXN * MAXN];
int pos[MAXN];
bool g[26][26];
void print_ans(bool ok) {
if (!ok) {
cout << "NE" << endl;
exit(0);
}
cout << "DA" << endl;
}
void read_input() {
cin >> n;
vector<int> ord(n);
vector<string> t(n);
rep(i, n) {
cin >> t[i];
}
rep(i, n) {
int x;
cin >> x;
x--;
s[i] = t[x];
}
pos[0] = -1;
}
void trie_add(const string &s, int i) {
int v = 0;
for (auto ch : s) {
ch -= 'a';
if (!to[v][ch]) {
to[v][ch] = last;
pos[last] = -1;
last++;
}
v = to[v][ch];
}
pos[v] = i;
}
void dfs(int v) {
mn[v] = INT_MAX;
mx[v] = INT_MIN;
sz[v] = 0;
if (pos[v] != -1) {
mn[v] = mx[v] = pos[v];
sz[v] = 1;
}
vector<pair<int, int>> arr;
rep(i, 26) {
if (to[v][i] == 0) continue;
int u = to[v][i];
dfs(u);
arr.push_back({mn[u], i});
mn[v] = min(mn[v], mn[u]);
mx[v] = max(mx[v], mx[u]);
sz[v] += sz[u];
}
if (mx[v] - mn[v] + 1 != sz[v] || (pos[v] != mn[v] && pos[v] != -1)) {
// cout << v << endl;
print_ans(false);
}
sort(all(arr));
for (int i = 1; i < arr.size(); ++i) {
g[arr[i - 1].s][arr[i].s] = true;
}
}
int col[26];
vector<int> ord;
void topsort(int v) {
col[v] = 1;
rep(to, 26) {
if (!g[v][to]) continue;
if (col[to] == 1) print_ans(false);
if (col[to] == 2) continue;
topsort(to);
}
col[v] = 2;
ord.push_back(v);
}
int main() {
FAST_IO;
read_input();
rep(i, n) {
trie_add(s[i], i);
}
dfs(0);
rep(i, 26) {
if (!col[25 - i]) {
topsort(25 - i);
}
}
reverse(all(ord));
cout << "DA" << endl;
assert(ord.size() == 26);
rep(i, 26) {
cout << char('a' + ord[i]);
}
cout << endl;
}
Compilation message
cezar.cpp: In function 'void trie_add(const string&, int)':
cezar.cpp:78:16: warning: array subscript has type 'char' [-Wchar-subscripts]
if (!to[v][ch]) {
^
cezar.cpp:79:12: warning: array subscript has type 'char' [-Wchar-subscripts]
to[v][ch] = last;
^
cezar.cpp:83:15: warning: array subscript has type 'char' [-Wchar-subscripts]
v = to[v][ch];
^
cezar.cpp: In function 'void dfs(int)':
cezar.cpp:118:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < arr.size(); ++i) {
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1112 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
