oj.uz

Submission #859819

# Submission time Handle Problem Language Result Execution time Memory
859819 2023-10-10T18:09:00 Z blackslex Type Printer (IOI08_printer) C++17
100 / 100
 109 ms 165536 KB 
#include<bits/stdc++.h>

using namespace std;
using tp = tuple<int, int, char>;

const int N = 3e4 + 5, C = 26;
int n, idx;
string s;
vector<char> ans;

struct node {
    int nxt[C], lv[C];
    bool end;
    node() {for (int i = 0; i < C; i++) nxt[i] = lv[i] = 0; end = 0;}
} t[N * C];

void add (string s) {
    int cur = 0;
    for (auto &e: s) e -= 'a';
    for (auto &e: s) {
        if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
    }
    t[cur].end = 1;
}

void dfs (int cur) {
    if (t[cur].end) ans.emplace_back('P');
    vector<tp> v;
    for (int i = 0; i < C; i++) if (t[cur].nxt[i]) v.emplace_back(t[cur].lv[i], t[cur].nxt[i], i + 'a');
    sort(v.begin(), v.end());
    for (auto &[lv, nxt, c]: v) ans.emplace_back(c), dfs(nxt), ans.emplace_back('-');
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) cin >> s, add(s);
    dfs(0);
    while (ans.back() == '-') ans.pop_back();
    printf("%d\n", ans.size());
    for (auto &e: ans) printf("%c\n", e);
}

Compilation message

printer.cpp: In function 'void add(std::string)':
printer.cpp:21:25: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |                         ^
printer.cpp:21:40: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |                                        ^
printer.cpp:21:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   21 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |         ^~
printer.cpp:21:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   21 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |                                                    ^
printer.cpp:21:62: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |                                                              ^
printer.cpp:21:81: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |                                                                                 ^
printer.cpp:21:119: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |         if (!t[cur].nxt[e]) t[cur].nxt[e] = ++idx; t[cur].lv[e] = max(t[cur].lv[e], (int) s.size()); cur = t[cur].nxt[e];
      |                                                                                                                       ^
printer.cpp: In function 'int main()':
printer.cpp:39:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wformat=]
   39 |     printf("%d\n", ans.size());
      |             ~^     ~~~~~~~~~~
      |              |             |
      |              int           std::vector<char>::size_type {aka long unsigned int}
      |             %ld
printer.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 162132 KB Output is correct
2 Correct 28 ms 162100 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 162128 KB Output is correct
2 Correct 28 ms 162132 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 162020 KB Output is correct
2 Correct 28 ms 162132 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 162128 KB Output is correct
2 Correct 28 ms 162228 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 162100 KB Output is correct
2 Correct 29 ms 162136 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 162136 KB Output is correct
2 Correct 31 ms 162640 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 162388 KB Output is correct
2 Correct 41 ms 162552 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 162708 KB Output is correct
2 Correct 36 ms 162384 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 163480 KB Output is correct
2 Correct 96 ms 165064 KB Output is correct
3 Correct 68 ms 163972 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 163396 KB Output is correct
2 Correct 109 ms 165536 KB Output is correct
3 Correct 77 ms 164080 KB Output is correct
4 Correct 98 ms 165280 KB Output is correct