제출 #1199427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199427		TahirAliyev	Type Printer (IOI08_printer)	C++20	100 / 100	113 ms	99248 KiB

printer

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
const int oo = 1e9 + 9;
const int MAX = 25000 + 5;

int t[30 * MAX][26];
int D[30 * MAX];
int cnt[30 * MAX];
int nxt = 2;
void add(string &s){
    int node = 1;
    for(int i = 0; i < s.size(); i++){
        D[node] = max((int)s.size() - i, D[node]);
        if(!t[node][s[i]-'a']) t[node][s[i]-'a'] = nxt++;
        node = t[node][s[i]-'a'];
    }
    cnt[node]++;
}

string ans = "";

void dfs(int node){
    if(cnt[node]) ans += 'P';
    vector<pii> v;
    for(int i = 0; i < 26; i++){
        if(!t[node][i]) continue;
        v.push_back({D[t[node][i]], i});
    } 
    sort(all(v));
    for(auto [d, c] : v){
        ans += ('a' + c);
        dfs(t[node][c]);
        ans += ('-');
    }
}

void solve(){
    int n; cin >> n;
    for(int i = 1; i <= n; i++){
        string s; cin >> s;
        add(s);
    }
    dfs(1);
    while(ans.back() == '-') ans.pop_back();
    cout << ans.size() << '\n';
    for(char c : ans) cout << c << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10