Submission #1232889

#TimeUsernameProblemLanguageResultExecution timeMemory
1232889lanaskaricaType Printer (IOI08_printer)C++20
100 / 100
70 ms42172 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define pii pair <int, int>
#define fi first
#define se second

const int MAXN = 1e6 + 5;

int cnt, d[MAXN];
bool ispisi[MAXN];
char slovo[MAXN];
string s;

vector <int> v[MAXN];
vector <char> rj;

void dodaj(int a, int idx) {
	if (idx >= s.size()) {ispisi[a] = 1; d[a] = max(d[a], 1); return;}
	
	int x = -1;
	for (auto e : v[a]) {
		if (slovo[e] == s[idx]) x = e; 
	}
	if (x == -1) {
		v[a].push_back(cnt);
		slovo[cnt] = s[idx];
		x = cnt; cnt++;
	}
	
	dodaj(x, idx + 1);
	d[a] = max(d[a], d[x] + 1); 
	//cout << a << " " << d[a] << " " << x << " " << d[x] << endl; 
}

void dfs(int a) {
	//cout << a << " " << d[a] << endl;
	if (ispisi[a] == 1) rj.push_back('P');
	int mx = 0, x = -1;
	for (auto e : v[a]) {
		if (d[e] > mx) {mx = d[e]; x = e;}
	}
	for (auto e : v[a]) {
		if (e == x) continue;
		rj.push_back(slovo[e]);
		dfs(e);
		rj.push_back('-');
	}
	if (x != -1) {
		rj.push_back(slovo[x]);
		dfs(x);
		rj.push_back('-');
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	cnt = 1;
	for (int i = 0; i < n; i++) {
		cin >> s; dodaj(0, 0);
	}
	
	dfs(0);
	
	int i = rj.size() - 1;
	while (rj[i] == '-') {rj.pop_back(); i--;} 
	
	cout << rj.size() << "\n";
	for (auto e : rj) cout << e << "\n";
	
	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...