제출 #1362598

#제출 시각아이디문제언어결과실행 시간메모리
1362598po_rag526Type Printer (IOI08_printer)C++20
0 / 100
36 ms26404 KiB
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define is insert
#define MSK(k) (1ULL << k)
#define ton(k, vt) (k|((1ULL) << vt))
#define bat(k, vt) ((k >> vt) & 1)
#define elif else if
#define PROBLEM ""
using namespace std;

/*
 /\_/\
(= ._.) ?
/ >0 \>1
*/
// #define and code:

const int maxN = 1e6;
int n;
struct node{
    int child[26], cnt;
};
node trie[maxN + 7];
string st, res;
int cnt, ans;
vector<int> g[maxN + 7];

void add(string &it){
    int cur = 0;
    for(const char &c : it){
        int id = c - 'a';
        if(!trie[cur].child[id]){
            trie[cur].child[id] = ++cnt;
        }
        cur = trie[cur].child[id];
    }
    trie[cur].cnt++;
}

int prepare(int u){
    vector<pair<int, int>> li;
    int hi = 0;
    for(int i = 0; i < 26; i++){
        if(trie[u].child[i]){
            int tmp = prepare(trie[u].child[i]);
            li.pb({tmp, i});
            hi = max(hi, tmp);
        }
    }
    sort(li.begin(), li.end());

    for(const pair<int, int> it : li){
        g[u].pb(it.second);
    }
    return hi + 1;
}

void dfs(int u){
    for(int i = 0; i < trie[u].cnt; i++){
        res += "P";
        ans++;
    }
    if(ans == n){
        cout << res.size() << '\n';
        cout << res;
        exit(0);
    }
    for(int v : g[u]){
        res += char(v + 'a');
        dfs(trie[u].child[v]);
        res += "-";
    }
}

int main() {
    // freopen(PROBLEM".inp", "r", stdin);
    // freopen(PROBLEM".out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> st;
        add(st);
    }

    prepare(0);
    dfs(0);

    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…