Submission #1319412

#TimeUsernameProblemLanguageResultExecution timeMemory
1319412algoproclubType Printer (IOI08_printer)C++20
100 / 100
88 ms54632 KiB
// UUID: 1527bd44-1076-4984-8652-204585d14b39
#include <bits/stdc++.h>
using namespace std;
const int MAXN=22*25000+1;
int trie[MAXN][26];
vector<int> word, utcs; vector<char> ki;
int cnt=1;
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'];
	}
	word[cur]=1;
}
void add2(string s){
	int cur=0;
	for(char z:s){
		if(!trie[cur][z-'a']) trie[cur][z-'a']=cnt++;
		utcs[cur]=z-'a';
		cur=trie[cur][z-'a'];
	}
	word[cur]=1;
}
void dfs(int x){
	if(word[x]) ki.push_back('P');
	for(int i=0; i<26; i++){
		if(!trie[x][i]||utcs[x]==i) continue;
		ki.push_back(i+'a');
		dfs(trie[x][i]);
		ki.push_back('-');
	}
	if(utcs[x]!=-1){
		ki.push_back(utcs[x]+'a');
		dfs(trie[x][utcs[x]]);
		ki.push_back('-');
	}
}
int main() {
	int n; cin>>n;
	vector<pair<int, string>> kak;
	word.resize(n*22+1, 0);
	utcs.resize(n*22+1, -1);
	for(int i=0; i<n; i++){
		string s; cin>>s; 
		kak.push_back({s.size(),s});
	}
	sort(kak.rbegin(), kak.rend());
	add2(kak[0].second);
	for(int i=1; i<n; i++) add(kak[i].second);
	dfs(0);
	while(ki.back()=='-')ki.pop_back();
	cout<<ki.size()<<"\n";
	for(auto x:ki) cout<<x<<"\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...