Submission #1195115

#TimeUsernameProblemLanguageResultExecution timeMemory
1195115damamilaType Printer (IOI08_printer)C++20
60 / 100
1091 ms34088 KiB
#include <bits/stdc++.h>

using namespace std;

const int maxn = 500005;

int g [maxn][26];
int sz [maxn][26];
bool fin [maxn];
int cnt = 2;
string ans;
int n;

void insrt(string s) {
	int idx = 1;
	for (int i = 0; i < s.size() ; i++) {
		int next = s[i]-'a';
		if (g[idx][next] == 0) {
			g[idx][next] = cnt;
			cnt++;
		}
		sz[idx][next] = max(sz[idx][next], (int)s.size());
		idx = g[idx][next];
	}
	fin[idx] = 1;
}

void dfs(int u) {
	if (fin[u]) {
		ans = ans+'P'+'\n';
		n--;
	}
	vector<tuple<int, int, int>> tmp;
	for (int i = 0; i < 26; i++) tmp.push_back({sz[u][i], i, g[u][i]});
	sort(tmp.begin(), tmp.end());
	for (auto [len, let, v] : tmp) {
		if (v == 0) continue;
		ans = ans+char('a'+let)+'\n';
		dfs(v);
		if (n > 0) ans = ans+'-'+'\n';
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);  
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		insrt(s);
	}
	dfs(1);
	cout << ans.size()/2 << '\n' << ans;
}
#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...