Submission #1195120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195120		damamila	Type Printer (IOI08_printer)	C++20	100 / 100	191 ms	92792 KiB

printer

#include <bits/stdc++.h>

using namespace std;

const int maxn = 500005;

int g [maxn][26];
int sz [maxn][26];
bool fin [maxn];
int cnt = 2;
string ans;
int n;

void insrt(string s) {
	int idx = 1;
	for (int i = 0; i < s.size() ; i++) {
		int next = s[i]-'a';
		if (g[idx][next] == 0) {
			g[idx][next] = cnt;
			cnt++;
		}
		sz[idx][next] = max(sz[idx][next], (int)s.size());
		idx = g[idx][next];
	}
	fin[idx] = 1;
}

void dfs(int u) {
	if (fin[u]) {
		ans.push_back('P');
		n--;
	}
	vector<tuple<int, int, int>> tmp;
	for (int i = 0; i < 26; i++) {
		if (g[u][i] != 0) tmp.push_back({sz[u][i], i, g[u][i]});
	}
	sort(tmp.begin(), tmp.end());
	for (auto [len, let, v] : tmp) {
		ans.push_back(char(let+'a'));
		dfs(v);
		if (n > 0) ans.push_back('-');
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);  
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		insrt(s);
	}
	dfs(1);
	cout << ans.size() << "\n";
	for (auto 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