제출 #1244475

#제출 시각아이디문제언어결과실행 시간메모리
1244475newsboyType Printer (IOI08_printer)C++20
80 / 100
74 ms66120 KiB
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <tuple>
#include <cassert>
#include <array>
#include <list>
#include <random>
#include <initializer_list>
#include <chrono>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;

constexpr i64 N = 3E5 + 10;
i64 trie[N][26], f[N], d[N];
i64 tot;

i64 newNode() {
    i64 x = ++tot;
    for (i64 i = 0; i < 26; i++) {
        trie[x][i] = 0;
    }
    f[x] = d[x] = 0;
    return x;
};

void init() {
    tot = 0;
    newNode();
}

void add(string s) {
    i64 o = 1;
    for (i64 i = 0; i < s.size(); i++) {
        i64& p = trie[o][s[i] - 'a'];
        if (!p) {
            p = newNode();
        }
        o = p;
    }
    f[o] = 1;
}

void solve() {
    init();
    i64 n;
    cin >> n;
    for (i64 i = 0; i < n; i++) {
        string s;
        cin >> s;
        add(s);
    }
    auto work = [&](auto& self, i64 x) -> void {
        for (i64 i = 0; i < 26; i++) {
            if (trie[x][i]) {
                self(self, trie[x][i]);
                d[x] = max(d[x], d[trie[x][i]] + 1);
            }
        }
        };
    work(work, 1);
    vector<char> ans;
    auto dfs = [&](auto& self, i64 x) -> void {
        if (f[x]) {
            ans.push_back('P');
        }
        vector<i64> id(26);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](i64 i, i64 j) {
            return d[trie[x][i]] < d[trie[x][j]];
            });
        for (auto i: id) {
            if (!trie[x][i]) {
                continue;
            }
            ans.push_back('a' + i);
            self(self, trie[x][i]);
            ans.push_back('-');
        }
        };
    dfs(dfs, 1);
    while (ans.back() == '-') {
        ans.pop_back();
    }
    cout << ans.size() << '\n';
    for (auto x : ans) {
        cout << char(x) << '\n';
    }
} 

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--) {
        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...