Submission #68833

#	Time	Username	Problem	Language	Result	Execution time	Memory
68833		forestryks	Cezar (COCI16_cezar)	C++14	20 / 100	4 ms	1124 KiB

cezar

///////////////////////////////////////////////////////////////////////////////////////////////
#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));

	string ans(26, '0');

	rep(i, 26) {
		ans[ord[i]] = 'a' + i;
	}

	cout << "DA" << endl;
	cout << ans << endl;

	// rep(i, 26) {
	// 	rep(j, 26) {
	// 		if (g[i][j]) {
	// 			cout << char('a' + i) << ' ' << char('a' + j) << endl;
	// 		}
	// 	}
	// }
}

Compilation message (stderr)

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) {
                  ~~^~~~~~~~~~~~

• 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: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10