Submission #656370

#	Time	Username	Problem	Language	Result	Execution time	Memory
656370		gamigafy	Type Printer (IOI08_printer)	C++17	100 / 100	155 ms	50792 KiB

printer

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

#define ll long long
#define sz(x) (int)(x.size())

const int N = 5e5+5;
int n, tot = 0;
char c[N];
bool last[N];
vector<char> ans;
int adj[N][26], dep[N];

void dfs(int u) {
	sort(adj[u], adj[u] + 26, [&](int i, int j) {
		return dep[i] < dep[j];
	});
	for(int i = 0; i < 26; i++) {
		if(adj[u][i]) {
			dfs(adj[u][i]);
		}
	}
}

void dfs2(int u) {
	for(int i = 0; i < 26; i++) {
		if(adj[u][i]) {
			ans.push_back(c[adj[u][i]]);
			if(last[adj[u][i]]) {
				ans.push_back('P');
			}
			dfs2(adj[u][i]);
			ans.push_back('-');
		}
	}
}

int main() {
	cin>>n;

	for(int i = 0; i < n; i++) {
		string s; cin>> s;
		int t = 0;
		for(int j = 0; j < sz(s); j++) {
			int p = s[j] - 'a';
			if(!adj[t][p])
				adj[t][p] = ++tot;
			t = adj[t][p];
			c[t] = s[j];
			dep[t] = max(dep[t], sz(s));
		}
		last[t] = true;
	}

	dfs(0);
	dfs2(0);

	while(ans.back() == '-') {
		ans.pop_back();
	}

	cout<<sz(ans)<<'\n';
	for(auto s : ans) {
		cout<<s<<'\n';
	}
	return 0;
}

• 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