제출 #1266810

#제출 시각아이디문제언어결과실행 시간메모리
1266810ThylOneType Printer (IOI08_printer)C++20
100 / 100
664 ms106012 KiB
//####################
//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;
	bool ed = false;
	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()){root->ed = true;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);
	if(r->ed)
		ans.push_back('P');
	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++;
		}
	}
	
	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;
};
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...