Submission #1319356

#TimeUsernameProblemLanguageResultExecution timeMemory
1319356linhnkType Printer (IOI08_printer)C++20
20 / 100
35 ms19336 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAXN=21*25000+1;
int trie[MAXN][26];
vector<int> word; vector<char> ki;
int cnt=1; char szent;
void add(string s){
	int cur=0;
	for(char z:s){
		if(!trie[cur][z-'a']) trie[cur][z-'a']=cnt++;
		cur=trie[cur][z-'a'];
		if(word[cur]==-1) word[cur]=0;
	}
	word[cur]++;
}
void dfs(int x){
	for(int i=0; i<26; i++){
		if(word[trie[x][i]]==-1||(x==0&&i==szent-'a')) continue;
		ki.push_back(i+'a');
		dfs(trie[x][i]);
	}
	if(word[x]>0) ki.push_back('P');
	if(x)ki.push_back('-');
}
void dfs2(int x){
	for(int i=0; i<26; i++){
		if(word[trie[x][i]]==-1) continue;
		ki.push_back(i+'a');
		dfs(trie[x][i]);
	}
	if(word[x]>0) ki.push_back('P');
	ki.push_back('-');
}
int main() {
	int n; cin>>n;
	vector<pair<int, char>> kak;
	word.resize(n*21+1, -1);
	for(int i=0; i<n; i++){
		string s; cin>>s; 
		add(s); kak.push_back({s.size(), s[0]});
	}
	sort(kak.rbegin(), kak.rend());
	szent=kak[0].second;
	dfs(0);
	ki.push_back(szent);
	dfs2(trie[0][szent-'a']);
	int a=ki.size()-1;
	while(ki[a]=='-') a--;
	cout<<a+1<<"\n";
	for(int i=0; i<=a; i++) cout<<ki[i]<<"\n";
}
#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...