Submission #367903

#	Time	Username	Problem	Language	Result	Execution time	Memory
367903		sinamhdv	Type Printer (IOI08_printer)	C++11	100 / 100	241 ms	96996 KiB

printer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const ll LINF = (ll)INF * INF;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod)
#define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'

#define MAXN 25100
#define MAXL 500100

int n;
string s[MAXN];
int tn = 1;
int trie[MAXL][26];
int order[MAXL][26];
bool eow[MAXL];
int maxh[MAXL];
vector<char> ops;

void add(const string &s)
{
	int v = 1;
	for (char c : s)
	{
		int b = c - 'a';
		if (!trie[v][b])
			trie[v][b] = ++tn;
		v = trie[v][b];
	}
	eow[v] = true;
}

void dfs1(int v)
{
	FOR(u, 0, 26)
	{
		if (!trie[v][u]) continue;
		dfs1(trie[v][u]);
		maxh[v] = max(maxh[v], maxh[trie[v][u]] + 1);
	}
}

int printed;

void dfs2(int v)
{
	if (eow[v])
	{
		printed++;
		ops.pb('P');
	}
	if (printed == n)
		return;
	FOR(u, 0, 26)
	{
		int c = order[v][u];
		if (c < 0) continue;
		ops.pb(c + 'a');
		dfs2(trie[v][c]);
		if (printed == n)
			return;
		ops.pb('-');
	}
}

int32_t main(void)
{
	fast_io;
	cin >> n;
	FOR(i, 0, n)
	{
		cin >> s[i];
		add(s[i]);
	}

	dfs1(1);

	FOR(v, 1, tn + 1)
	{
		memset(order[v], -1, sizeof(order[v]));
		vector<int> vec;
		FOR(j, 0, 26)
			if (trie[v][j])
				vec.pb(j);

		sort(all(vec), [&](int x, int y) { return maxh[trie[v][x]] < maxh[trie[v][y]]; });
		FOR(j, 0, (int)vec.size())
			order[v][j] = vec[j];
	}

	dfs2(1);

	cout << ops.size() << endl;

	for (char c : ops)
		cout << c << endl;

	return 0;
}

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