Submission #756926

#	Time	Username	Problem	Language	Result	Execution time	Memory
756926		SanguineChameleon	Type Printer (IOI08_printer)	C++17	100 / 100	204 ms	106556 KiB

printer

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct node {
	node *ch[26] = {};
	bool flag = false;
	int mx = 0;
	int best = -1;
};

node *root = new node();

void dfs1(node *cur) {
	for (int i = 0; i < 26; i++) {
		if (cur->ch[i]) {
			dfs1(cur->ch[i]);
		}
	}
	for (int i = 0; i < 26; i++) {
		if (cur->ch[i] && cur->ch[i]->mx + 1 > cur->mx) {
			cur->mx = cur->ch[i]->mx + 1;
			cur->best = i;
		}
	}
}

vector<char> res;

void dfs2(node *cur, bool up) {
	if (cur->flag) {
		res.push_back('P');
	}
	if (cur->best != -1) {
		for (int i = 0; i < 26; i++) {
			if ((up || i != cur->best) && cur->ch[i]) {
				res.push_back((char)('a' + i));
				dfs2(cur->ch[i], true);
				res.push_back('-');
			}
		}
		if (!up) {
			res.push_back((char)('a' + cur->best));
			dfs2(cur->ch[cur->best], false);
		}
	}
}

void just_do_it() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		node *cur = root;
		for (auto c: s) {
			int d = c - 'a';
			if (!cur->ch[d]) {
				cur->ch[d] = new node();
			}
			cur = cur->ch[d];
		}
		cur->flag = true;
	}
	dfs1(root);
	dfs2(root, false);
	cout << res.size() << '\n';
	for (auto c: res) {
		cout << c << '\n';
	}
}

• 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