제출 #1354186

#제출 시각아이디문제언어결과실행 시간메모리
1354186nagorn_phType Printer (IOI08_printer)C++20
100 / 100
106 ms104584 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)
#define matrix vector <vector <int>>
#define mat(n, m) vector <vector <int>> (n, vector <int> (m));

const int mod = 1e9 + 7;
const int inf = 1e18;
const matrix II = {{1, 0}, {0, 1}};
const int N = 25005;

int n, tri[N*20][26], finish[N*20], idx = 1;
pii heavy[N * 26];
string s[N];

void update(string s){
    int u = 1;
    for (auto c : s) {
        if (tri[u][c - 'a'] == 0) tri[u][c - 'a'] = ++idx;
        u = tri[u][c - 'a'];
    }
    finish[u] = 1;
}

void dfs1(int u){
    for (int i = 0; i < 26; i++) {
        if (!tri[u][i]) continue;
        dfs1(tri[u][i]);
        heavy[u] = max(heavy[u], {heavy[tri[u][i]].first + 1, tri[u][i]});
    }
}

vector <char> ans;

void dfs2(int u){
    if (finish[u]) ans.emb('P');
    char c;
    for (int i = 0; i < 26; i++) {
        if (tri[u][i] == heavy[u].second) c = (i + 'a');
        if (!tri[u][i] || heavy[u].second == tri[u][i]) continue;
        ans.emb((char)(i + 'a'));
        dfs2(tri[u][i]);
        ans.emb('-');
    }
    if (heavy[u].second) {
        ans.emb(c);
        dfs2(heavy[u].second);
        ans.emb('-');
    }
}

void solve(){
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        update(s[i]);
    }
    dfs1(1);
    dfs2(1);
    while (ans.back() == '-') ans.pop_back();
    cout << ans.size() << "\n";
    for (auto e : ans) cout << e << "\n";
}

int32_t main(){
    iShowSpeed;
    // int q; cin >> q; while (q--) 
    solve();
}
#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...