Submission #310574

#	Time	Username	Problem	Language	Result	Execution time	Memory
310574		Temmie	Type Printer (IOI08_printer)	C++17	100 / 100	167 ms	72300 KiB

printer

#include <bits/stdc++.h>

int n, ind = 1;
std::vector <char> ans;
std::vector <int> par(5e5);
std::vector <std::vector <int>> tr(5e5, std::vector <int> (26, -1));
std::vector <bool> vis(5e5, false), tak(5e5, false);

int add(const std::string& s) {
	int r = 0;
	for (const char& c : s) {
		if (tr[r][c - 'a'] == -1) tr[r][c - 'a'] = ind, par[ind++] = r;
		r = tr[r][c - 'a'];
	}
	vis[r] = true;
	return r;
}

void dfs(int now = 0) {
	if (vis[now]) ans.push_back('P');
	char ch;
	int other = -1;
	for (int i = 0; i < 26; i++) {
		if (tr[now][i] == -1) continue;
		char c = i + 'a';
		if (tak[tr[now][i]]) ch = c, other = tr[now][i];
		else ans.push_back(c), dfs(tr[now][i]), ans.push_back('-');
	}
	if (other != -1) ans.push_back(ch), dfs(other);
}

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	std::cin >> n;
	int l = 0, node = -1;
	par[0] = -1;
	for (int i = 0; i < n; i++) {
		std::string s; std::cin >> s;
		int now = add(s);
		if ((int)s.length() > l) l = s.length(), node = now;
	}
	while ((node) >= 0) tak[node] = true, node = par[node];
	dfs();
	std::cout << ans.size() << "\n";
	for (char c : ans) std::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