Submission #1248175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248175		pasta	Type Printer (IOI08_printer)	C++20	100 / 100	109 ms	54496 KiB

printer

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

#define pb	push_back
const int maxn = 1e6 + 10;

int n, vt = 1;
int G[maxn][26], cnt[maxn], dp[maxn], h[maxn], par[maxn];

void add(string s) {
	int v = 1;
	for (char c : s) {
		c -= 'a';
		if (!G[v][c]) {
			G[v][c] = ++vt;
			par[vt] = v;
			h[vt] = h[v] + 1;
			dp[v] = max(dp[v], h[vt]);
		}
		v = G[v][c];
	}
	cnt[v]++;
	while (v != 1) {
		// cout << v << '\n';
		dp[par[v]] = max(dp[par[v]], dp[v]);
		v = par[v];
	}
}

vector<char> ans;

void dfs(int v) {
	while (cnt[v]--)
		ans.pb('P');
	
	int mx = 0, id = 0;
	for (int i = 0; i < 26; i++) {
		if (!G[v][i]) continue;
		int u = G[v][i];
		if (dp[u] == dp[v] && mx == 0) {
			mx = u;
			id = i;
			continue;
		}
		ans.pb(char(i + 'a'));
		dfs(u);
	}
	if (mx > 0) {
		ans.pb(char(id + 'a'));
		dfs(mx);
	}
	ans.pb('-');
}

signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		add(s);
	}
	dfs(1);
	while (ans.back() == '-')
		ans.pop_back();
	cout << ans.size() << '\n';
	for (char x : ans)
		cout << x << '\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