This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define F first
#define S second
#define SZ(x) int((x).size())
const char nl = '\n';
using ll = long long;
using namespace std;
const int N = 25100;
int nam = 0;
int trie[N][27];
int dp[N][27];
bool visited[N][27];
void add(int x, string s, int pos) {
if (pos >= SZ(s)) return ;
char c = s[pos];
if (trie[x][c-'a'] == 0) {
trie[x][c-'a'] = ++nam;
}
add(trie[x][c-'a'], s, pos + 1);
// cout << x << " " << trie[x][c-'a'] << nl;
if (pos + 1 == SZ(s)) {
dp[x][c-'a'] = 1;
} else {
dp[x][c-'a'] += dp[trie[x][c-'a']][s[pos+1]-'a'] + !visited[x][c-'a'];
visited[x][c-'a'] = true;
}
}
vector<char> res;
vector<pair<int, pair<int, int>>> mn[N];
void PP(int x) {
if (!x) return ;
res.push_back('P');
for (int i = 0; i < x; i ++) {
res.push_back('-');
}
}
void dfs(int x) {
// cout << x << nl;
int fine = 0;
for (auto el : mn[x]) {
PP(fine);
res.push_back(el.S.F + 'a');
if (SZ(mn[el.S.S]) > 0) {
dfs(el.S.S);
}
fine = el.F;
}
}
void verkefni() {
int n;
cin >> n;
string s[n];
for (int i = 0; i < n; i ++) {
cin >> s[i];
add(0, s[i], 0);
}
for (int i = 0; i < N; i ++) {
for (int j = 0; j < 27; j ++) {
visited[i][j] = false;
}
}
for (int i = 0; i <= nam; i ++) {
for (int j = 0; j < 27; j ++) {
if (dp[i][j]) {
mn[i].push_back({dp[i][j], {j, trie[i][j]}});
}
}
}
for (int i = 0; i <= nam; i ++) {
sort(mn[i].begin(), mn[i].end());
}
dfs(0);
res.push_back('P');
cout << SZ(res) << nl;
for (auto c : res) {
cout << c << nl;
}
// for (int i = 0; i <= nam; i ++) {
// for (auto el : mn[i]) {
// cout << "(" << el.F << " " << el.S.F << " " << el.S.S << ") ";
// }
// cout << nl;
// }
// for (int i = 0; i < nam; i ++) {
// for (int j = 0; j < 27; j ++) {
// if (trie[i][j]) {
// cout << "[" << i << ", " << j << "] --> " << trie[i][j] << " | " << dp[i][j] << nl;
// }
// }
// }
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tst = 1;
// cin >> tst;
while (tst --) {
verkefni();
cout << nl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |