Submission #1336959

#TimeUsernameProblemLanguageResultExecution timeMemory
1336959lxz20071231Type Printer (IOI08_printer)C++20
60 / 100
7 ms3652 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long; using db = double; using i128 = __int128_t;
template <class T> using v = vector<T>;
using pii = pair<int, int>; using vi = v<int>; using vpi = v<pii>; using vvi = v<vi>; using vvpi = v<vpi>;
using pll = pair<ll, ll>; using vll = v<ll>; using vpl = v<pll>; using vvl = v<vll>; using vvpl = v<vpl>;

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()

const int INF = 1e9;
const ll INFLL = 1e18;

const int N = 25005, C=30;
int to[N][C], cnt=0, dp[C*N], dep[C*N];
bool p[C*N];

string letter = "abcdefghijklmnopqrstuvwxyz";
v<char> op;

void md(int u){
    dp[u] = dep[u];
    for (int i=0; i<C; i++){
        int v = to[u][i];
        if (v){
            dep[v] = dep[u]+1;
            md(v);
            dp[u] = max(dp[u], dp[v]);
        }
    }
}

void dfs(int u){
    if (p[u]){
        op.pb('P');
    }
    vpi child;
    for (int i=0; i<C; i++){
        if (to[u][i]){
            child.pb({dp[to[u][i]], i});
        }
    }
    sort(all(child));
    for (pii e : child){
        op.pb(letter[e.s]);
        dfs(to[u][e.s]);
        op.pb('-');
    }
}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n; cin >> n;
    for (int i=1; i<=n; i++){
        string a; cin >> a;
        int u = 0;
        for (int i : a){
            int l = i-97;
            if (to[u][l] == 0){
                to[u][l] = ++cnt;
            }
            u = to[u][l];
        }
        p[u] = true;
    }

    md(0);
    dfs(0);

    while (op.back() == '-') op.pop_back();
    cout << op.size() << '\n';
    for (char i : op){
        cout << i << '\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...