Submission #1326573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326573		crispxx	Type Printer (IOI08_printer)	C++20	100 / 100	122 ms	107832 KiB

printer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct node {
	char c;
	
	bool flag;
	
	int d, mxd;
	
	node *ch[26];
	
	node(char c = ' ', bool flag = false, int d = 0, int mxd = 0, bool last = false) : c(c), flag(flag), d(d), mxd(mxd) {
		for(int i = 0; i < 26; i++) {
			ch[i] = NULL;
		}
	}
};

void add(node *root, const string &s) {
	node *cur = root;
	
	for(auto &c : s) {
		if(cur -> ch[c - 'a'] == NULL) {
			cur -> ch[c - 'a'] = new node(c);
		}
		
		cur = cur -> ch[c - 'a'];
	}
	
	cur -> flag = true;
}

void solve() {
	int n; cin >> n;
	
	vector<string> s(n);
	
	node *root = new node();
	
	for(auto &str : s) {
		cin >> str;
		add(root, str);
	}
	
	{
		auto dfs = [&](auto &&self, node *cur) -> void {
			cur -> mxd = cur -> d;
			
			for(int i = 0; i < 26; i++) {
				if(cur -> ch[i] != NULL) {
					cur -> ch[i] -> d = cur -> d + 1;
					self(self, cur -> ch[i]);
					cur -> mxd = max(cur -> mxd, cur -> ch[i] -> mxd);
				}
			}
		};
		
		dfs(dfs, root);
	}
	
	
	vector<char> ans;
	
	{
		auto dfs = [&](auto &&self, node *cur) -> void {
			int j = -1;
			
			for(int i = 0; i < 26; i++) {
				if(cur -> ch[i] != NULL && cur -> ch[i] -> mxd == root -> mxd) {
					j = i;
					break;
				}
			}
			
			if(cur -> c != ' ') ans.push_back(cur -> c);
			
			if(cur -> flag) ans.push_back('P');
			
			for(int i = 0; i < 26; i++) {
				if(cur -> ch[i] != NULL && i != j) {
					self(self, cur -> ch[i]);
				}
			}
			
			if(j != -1) self(self, cur -> ch[j]);
			
			if(cur -> c != ' ') ans.push_back('-');
		};
		
		dfs(dfs, root);
	}
	
	while(!ans.empty() && ans.back() == '-') ans.pop_back();
	
	cout << ans.size() << '\n';
	
	for(auto &c : ans) cout << c << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}

• 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