제출 #1311871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311871		algoproclub	Type Printer (IOI08_printer)	C++20	100 / 100	97 ms	67704 KiB

printer

// UUID: 4cce61c1-db47-4627-8e39-9d46edf2b03e
#include <iostream>
#include <vector>
using namespace std;

struct node {
	vector <int> v;
	bool endpoint = false;
	int last;
	node() {
		v.assign(26, 0);
		endpoint = false;
		last = -1;
	}
};

int n;
vector <string> w(3e4);
vector <node> t(1, node());
string ans;

void add(string s, bool l) {
	int x = 0, i;
	for (char c : s) {
		i = c - 'a';
		if (!t[x].v[i]) {
			t[x].v[i] = t.size();
			t.push_back(node());
		}
		if (l) t[x].last = i;
		x = t[x].v[i];
	}
	t[x].endpoint = true;
}

void dfs(int x) {
	if (t[x].endpoint) ans.push_back('P');
	for (int i = 0; i < 26; i++) {
		if (i == t[x].last || !t[x].v[i]) continue;
		ans.push_back('a' + i);
		dfs(t[x].v[i]);
		ans.push_back('-');
	}
	if (t[x].last > -1) {
		int i = t[x].last;
		ans.push_back('a' + i);
		dfs(t[x].v[i]);
		ans.push_back('-');
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int longest = 0;
	for (int i = 0; i < n; i++) {
		cin >> w[i];
		if (w[i].size() > w[longest].size()) longest = i;
	}
	for (int i = 0; i < n; i++) add(w[i], i == longest);
	dfs(0);
	while (ans.back() == '-') ans.pop_back();
	cout << ans.size() << "\n";
	for (char c : ans) 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