Submission #1107571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107571		vjudge1	Type Printer (IOI08_printer)	C++17	100 / 100	140 ms	103624 KiB

printer

#include <bits/stdc++.h>
#define int long long

using namespace std;

int trie[500002][26], d[500002], mx[500002], id=0, end_[500002];
constexpr int ROOT = 0;
vector<char> ans;

void dfs(int depth = 0, int cur = ROOT) {
	d[cur] = depth;
	mx[cur] = d[cur];
	for (int i = 0; i < 26; i++) {
		if (!trie[cur][i])
			continue;
		dfs(depth + 1, trie[cur][i]);
		mx[cur] = max(mx[cur], mx[trie[cur][i]]);
	}
}   

void dfs_ans(int cur = ROOT) {
	if (end_[cur])
		ans.push_back('P');
	for (int c = 0; c < 26; c++) {
		if (!trie[cur][c] || mx[cur] == mx[trie[cur][c]])
			continue;
		ans.push_back('a' + c);
		dfs_ans(trie[cur][c]);
	}
	for (int c = 0; c < 26; c++) {
		if (!trie[cur][c] || mx[cur] != mx[trie[cur][c]])
			continue;
		ans.push_back('a' + c);
		dfs_ans(trie[cur][c]);
	}
	ans.push_back('-');	
}

void add_string(string const & s) {
	int cur = ROOT;
	for (auto & c : s) {
		int x = c - 'a';
		if (trie[cur][x]) {
			cur = trie[cur][x];
		} else {
			cur = trie[cur][x] = ++id;
		}
	}
	end_[cur] = 1;
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int n; cin >> n;
	string s;
	for (int i = 0; i < n; i++)
		cin >> s, add_string(s);
	dfs(); dfs_ans();
	while(ans.back() != 'P')
		ans.pop_back();
	cout << (int) ans.size() << '\n';
	for (int i = 0; i < (int) ans.size(); i++) 
		cout << ans[i] << '\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