제출 #1274195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274195		dhuyyyy	Type Printer (IOI08_printer)	C++20	100 / 100	141 ms	123604 KiB

printer

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;

const int N = 1e6+5;
const int INF = 1e9;
const int MOD = 998244353;  

int n, m, u, timer = 0;

int trie[N][27], dp[N], num[N];

bool check[N];

string s;

vector <aa> adj[N];

vector <char> operations;

void add(string s){
    u = 0;
    for (char c : s){
        if (trie[u][c - 'a'] == 0) trie[u][c - 'a'] = ++timer;
        u = trie[u][c - 'a'];
    }
    check[u] = 1;
}
void get(int u, int cur){
    num[u] = cur;
    for (int j = 0; j <= 25; j++){
        if (trie[u][j]){
            get(trie[u][j],cur + 1);
            num[u] = max(num[u],num[trie[u][j]]);
        }
    }
    for (int j = 0; j <= 25; j++){
        if (trie[u][j]){
            adj[u].push_back({num[trie[u][j]],trie[u][j],j});
        }
    }
    sort(adj[u].begin(),adj[u].end());
}
void dfs(int u){
    if (check[u]) operations.push_back('P');
    for (aa it : adj[u]){
        operations.push_back(it[2] + 'a');
        dfs(it[1]);
    }
    operations.push_back('-');
}
signed main()
{   
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> s;
        add(s);
    }
    get(0,0);
    dfs(0);
    while (operations.back() == '-') operations.pop_back();
    cout << (int)operations.size() << '\n';
    for (int i = 0; i < (int)operations.size(); i++){
        cout << operations[i];
        if (i < (int)operations.size() - 1) cout << '\n';
    }
    return 0;
}
/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░              ░██████╗██╗██╗░░░██╗                ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░              ██╔════╝██║██║░░░██║                ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░              ╚█████╗░██║██║░░░██║                ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗              ░╚═══██╗██║██║░░░██║                ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝              ██████╔╝██║╚██████╔╝                ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░              ╚═════╝░╚═╝░╚═════╝░                ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/

• 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