Submission #1266807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266807		ThylOne	Type Printer (IOI08_printer)	C++20	20 / 100	246 ms	36464 KiB

printer

//####################
//TypePrinter
//####################
#include<bits/stdc++.h> 
#include <string_view>


#define all(x) x.begin(), x.end()
#define eb emplace_back
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
 
using namespace std;
struct trie{
	char val;
	int maxi_d=0;
	trie* fils[26];
	trie(char v):val(v){
		maxi_d = 0;
		for(int i = 0 ; i < 26 ; i++)
			fils[i]=nullptr;
	}
	inline trie* getFils(char c){
		assert(c >= 'a' && c <= 'z');
		return fils[c-'a'];
	}
};
void addWord(trie* root, string str,int l=0){
	if(l == str.size())return;

	root->maxi_d = max(root->maxi_d, (int)str.size() - l);
	auto f = root -> getFils(str[l]);
	if(f == nullptr){
		root -> fils[str[l] - 'a'] = new trie(str[l]);
		f = root->getFils(str[l]);
	}
	addWord(f, str, l + 1);
}

vector<char> ans;
void dfs(trie *r){
	if(r->val != '@')
		ans.push_back(r->val);
	int cnt = 0;
	for(char c = 'a' ; c <= 'z' ; c++){
		if(r->getFils(c) && r->maxi_d != r->getFils(c)->maxi_d + 1){
			dfs(r->getFils(c));
			cnt++;
		}
	}
	for(char c = 'a' ; c <= 'z' ; c++){
		if(r->getFils(c) && r->maxi_d == r->getFils(c)->maxi_d + 1){
			dfs(r->getFils(c));
			cnt++;
		}
	}
	if(cnt==0)
		ans.push_back('P');
	ans.push_back('-');
}
void clean(trie *r){
	if(!r)return;
	for(char c = 'a' ; c <= 'z' ; c++){
		clean(r->getFils(c));
	}
	delete r;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;cin>>n;
	trie* r = new trie('@');
	for(int i = 0 ; i < n ; i++){
		string str;cin>>str;
		addWord(r, str);
	}
	dfs(r);
	while(ans.back()=='-')ans.pop_back();
	cout << ans.size() << endl;
	for(auto c:ans)cout << c << endl;
	clean(r);
	return 0;
};

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10