Submission #1014365

#TimeUsernameProblemLanguageResultExecution timeMemory
1014365EntityPlanttType Printer (IOI08_printer)C++17
100 / 100
149 ms106552 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

string oper;
struct trie {
	trie *ch[26] = {};
	int mxdepth = 0, subtsize = 0;
	bool isword = false;
	void insert(string &s) {
		trie *node = this;
		for (char &c : s) {
			int idx = c - 'a';
			if (!node->ch[idx]) node->ch[idx] = new trie();
			node->subtsize++;
			node = node->ch[idx];
		}
		node->isword = true;
	}
	void calcmxdepth() {
		for (int i = 0; i < 26; i++) {
			if (!ch[i]) continue;
			ch[i]->calcmxdepth();
			mxdepth = max(mxdepth, ch[i]->mxdepth + 1);
		}
	}
	void construct() {
		if (isword) oper += 'P';
		vector <int> order;
		for (int i = 0; i < 26; i++) if (ch[i]) order.push_back(i);
		sort(order.begin(), order.end(), [&](int &a, int &b) {
			return ch[a]->mxdepth < ch[b]->mxdepth;
		});
		for (int &i : order) {
			oper += char(i + 'a');
			ch[i]->construct();
			oper += '-';
		}
	}
} t;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		t.insert(s);
	}
	t.calcmxdepth();
	t.construct();
	while (oper.back() == '-') oper.pop_back();
	cout << oper.size();
	for (char &c : oper) cout << '\n' << c;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...