Submission #1091922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091922		vjudge1	Type Printer (IOI08_printer)	C++17	100 / 100	961 ms	58548 KiB

printer

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

const int maxchar = 26;
int nums = 0, n;
vector<char> ret;
string longest = "";
struct Vertex {
    int next[maxchar];
    bool output = false;
    int priority = 0;
    Vertex() {
        fill(next, next + maxchar, -1);
    }
};

vector<Vertex> trie(1);

void add(string s) {
    int v = 0;
    for (char ch: s) {
        int c = ch - 'a';
        if (trie[v].next[c] == -1) {
            trie[v].next[c] = trie.size();
            trie.emplace_back();
        }
        v = trie[v].next[c];
    }
    trie[v].output = true;
}

void update(string s){
    int v = 0;
    for (int i = 0;i<s.length();i++){
        v = trie[v].next[(int) s[i] - 'a'];
        trie[v].priority = 1;
    }
}

void dfs(int v) {
    if (trie[v].output){
        ret.push_back('P');
        nums++;
    }
    int priority = -1;
    int idx = -1;
    for (int i = 0; i < maxchar; i++) {
        if (trie[v].next[i] != -1){
            // cout<<trie[v].next[i] << trie[trie[v].next[i]].priority<<endl;
            if (!trie[trie[v].next[i]].priority) {
            ret.push_back((char)i + 'a');
            dfs(trie[v].next[i]);
            
            }else {
                priority = trie[v].next[i];
                idx = i;
            }
        }
    }
    if (priority != -1){
        ret.push_back((char) idx + 'a');
        dfs(priority);
    }
    if (nums < n) {
        ret.push_back('-');
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        if (word.length() > longest.length()){
            longest = word;
        }
        add(word);
    }
    update(longest);
    dfs(0);
    cout<<ret.size()<<endl;
    for (auto i:ret){
        cout<<i<<endl;
    }
}

Compilation message (stderr)

printer.cpp: In function 'void update(std::string)':
printer.cpp:34:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0;i<s.length();i++){
      |                    ~^~~~~~~~~~~

• 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