제출 #1014365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1014365		EntityPlantt	Type Printer (IOI08_printer)	C++17	100 / 100	149 ms	106552 KiB

printer

#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;
}

• 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