Submission #855142

#	Time	Username	Problem	Language	Result	Execution time	Memory
855142		vjudge1	Type Printer (IOI08_printer)	C++17	100 / 100	74 ms	49932 KiB

printer

// Problem: D - Type Printer
// Contest: Virtual Judge - 2023榕阳提高级国庆集训-day1
// URL: https://vjudge.net/contest/584200#problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
#include <bits/stdc++.h>
using namespace std;

const int SIG = 26, NN = 25000;

struct Node
{
	int	 ch[SIG];
	bool mark, end;
} T[NN * 20];

int sz = 0;

void insert(const string &s)
{
	int u = 0;
	for (char c : s)
	{
		int d = c - 'a', &cu = T[u].ch[d];
		if (!cu)
			cu = ++sz;
		u = cu;
	}
	T[u].end = true;
}

void dfs(int u, string &ans)
{
	const Node &x = T[u];
	if (x.end)
		ans += 'P';
	int mi = -1;
	for (int i = 0; i < SIG; ++i)
	{
		int v = x.ch[i];
		if (!v)
			continue;
		if (T[v].mark)
			mi = i;
		else
			ans += i + 'a', dfs(v, ans);
	}
	if (mi != -1)
		ans += mi + 'a', dfs(x.ch[mi], ans);
	ans += '-';
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n;
	cin >> n;
	string s, l;
	for (int i = 0; i < n; ++i)
	{
		cin >> s, insert(s);
		if (s.length() > l.length())
			l = s;
	}
	for (size_t i = 0, u = 0; i < l.size(); i++)
		u = T[u].ch[l[i] - 'a'], T[u].mark = true;
	s.clear(), dfs(0, s);
	while (s.back() == '-')
		s.pop_back();
	cout << s.size() << "\n";
	for (char c : s)
		cout << c << "\n";
	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