Submission #1265796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265796		canhnam357	Type Printer (IOI08_printer)	C++20	100 / 100	104 ms	106984 KiB

printer

// source problem : 
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
#define MASK(i) (1LL << (i))
void ckmax(int& f, int s)
{
	f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
	f = (f < s ? f : s);
}
struct Trie
{
	int cnt, e, mx;
	Trie* child[26];
	Trie()
	{
		mx = 0;
		e = 0;
		cnt = 0;
		for (int i = 0; i < 26; i++) child[i] = NULL;
	}
};
Trie* p = new Trie();
void insert(string s)
{
	auto t = p;
	for (char c : s)
	{
		if (!t->child[c - 'a']) t->child[c - 'a'] = new Trie();
		t = t->child[c - 'a'];
		t->cnt++;
		ckmax(t->mx, (int)s.size());
	}
	t->e++;
}
string ans = "";
void get(Trie* cur)
{
	if (cur->e)
	{
		ans += 'P';
	}	
	vector<pair<int, int>> s;
	for (int i = 0; i < 26; i++)
	{
		if (cur->child[i])
		{
			s.emplace_back(cur->child[i]->mx, i);
		}
	}
	sort(s.begin(), s.end());
	for (auto [fi, se] : s)
	{
		ans += (char)('a' + se);
		get(cur->child[se]);
		ans += '-';
	}
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		insert(s);
	}
	get(p);
	string s = ans;
	while (!s.empty() && s.back() == '-') s.pop_back();
	cout << s.size() << '\n';
	for (char c : s) cout << c << '\n';
	return 0;
}
// n + tot_size * 2 - 2 * tot_lcp_adj - longest_sz

• 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