oj.uz

Submission #1091922

# Submission time Handle Problem Language Result Execution time Memory
1091922 2024-09-22T15:14:43 Z vjudge1 Type Printer (IOI08_printer) C++17
100 / 100
 961 ms 58548 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 608 KB Output is correct
2 Correct 8 ms 1020 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1304 KB Output is correct
2 Correct 19 ms 2388 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 4044 KB Output is correct
2 Correct 117 ms 7828 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 7880 KB Output is correct
2 Correct 42 ms 2388 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 29376 KB Output is correct
2 Correct 819 ms 58548 KB Output is correct
3 Correct 413 ms 29636 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 15524 KB Output is correct
2 Correct 961 ms 58492 KB Output is correct
3 Correct 496 ms 29624 KB Output is correct
4 Correct 948 ms 58524 KB Output is correct