제출 #1315186

#제출 시각아이디문제언어결과실행 시간메모리
1315186algoproclubType Printer (IOI08_printer)C++20
80 / 100
44 ms35668 KiB
// UUID: e07f11e5-6715-4217-9d0b-34563f46f499
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> trie(2.5e5+1, vector<int>(26, 0));
vector<bool> word_end(2.5e5+1, false);
vector<int> utso(2.5e5+1, -1);
string ans = "";

int cmt = 1;

void add(string word, bool last){
	int x = 1;
	for(char c: word){
		int j = c - 'a';
		if(!trie[x][j]){
			cmt++;
			trie[x][j] = cmt;
		}
		if(last) utso[x] = j;
		x = trie[x][j];
	}
	word_end[x] = true;
}

void dfs(int csucs){
	if(word_end[csucs]) ans += 'P';
	for(int i = 0; i < 26; i++){
		if(utso[csucs] == i || trie[csucs][i] == 0){
			continue;
		}
		ans += char(i+'a');
		dfs(trie[csucs][i]);
		ans += '-';
	}
	if(utso[csucs] != -1){
		ans += char(utso[csucs]+'a');
		dfs(trie[csucs][utso[csucs]]);
		ans += '-';
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	string mx_word = "";
	for(int i = 0; i < n; i++){
		string s;
		cin >> s;
		add(s, false);
		if(s.size() > mx_word.size()){
			mx_word = s;
		}
	}
	add(mx_word, true);
	dfs(1);
	while(ans[ans.size()-1] == '-') ans.pop_back();
	cout << ans.size() << "\n";
	for(char c: ans){
		cout << c << "\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...