제출 #1324112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324112		sh_qaxxorov_571	Type Printer (IOI08_printer)	C++20	100 / 100	134 ms	99092 KiB

printer

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Node {
    Node* child[26];
    bool isEndOfWord;
    int maxDepth;
    Node() {
        for (int i = 0; i < 26; i++) child[i] = nullptr;
        isEndOfWord = false;
        maxDepth = 0;
    }
};
void insert(Node* root, const string& s) {
    Node* curr = root;
    for (char c : s) {
        int idx = c - 'a';
        if (!curr->child[idx]) curr->child[idx] = new Node();
        curr = curr->child[idx];
    }
    curr->isEndOfWord = true;
}
int computeMaxDepth(Node* curr) {
    int m = 0;
    for (int i = 0; i < 26; i++) {
        if (curr->child[i]) {
            m = max(m, 1 + computeMaxDepth(curr->child[i]));
        }
    }
    return curr->maxDepth = m;
}
vector<char> operations;
void solve(Node* curr) {
    if (curr->isEndOfWord) {
        operations.push_back('P');
    }
    vector<pair<int, int>> children;
    for (int i = 0; i < 26; i++) {
        if (curr->child[i]) {
            children.push_back({curr->child[i]->maxDepth, i});
        }
    }
    sort(children.begin(), children.end());
    for (auto& p : children) {
        int idx = p.second;
        operations.push_back(idx + 'a');
        solve(curr->child[idx]);
        operations.push_back('-'); 
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    Node* root = new Node();
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        insert(root, s);
    }
    computeMaxDepth(root);
    solve(root);
    while (!operations.empty() && operations.back() == '-') {
        operations.pop_back();
    }
    cout << operations.size() << "\n";
    for (char op : operations) {
        cout << op << "\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