oj.uz

Submission #1043036

# Submission time Handle Problem Language Result Execution time Memory
1043036 2024-08-03T18:19:56 Z Zicrus Type Printer (IOI08_printer) C++17
100 / 100
 196 ms 101304 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct node {
public:
    unordered_map<char, node*> adj;
    bool end;
};

node *trie;
vector<char> res;
string longest;

void dfs(node *cur, int id) {
    for (auto &e : cur->adj) {
        if (id != -1 && e.first == longest[id]) continue;
        res.push_back(e.first);
        if (e.second->end) res.push_back('P');
        dfs(e.second, -1);
    }
    if (id != -1 && cur->adj.count(longest[id])) {
        res.push_back(longest[id]);
        if (cur->adj[longest[id]]->end) res.push_back('P');
        dfs(cur->adj[longest[id]], id+1);
    }
    res.push_back('-');
}

void solve() {
    dfs(trie, 0);
}

int main() {
    ll n;
    cin >> n;
    trie = new node();
    longest = "";
    vector<node*> gc = {trie};
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s.size() > longest.size()) longest = s;
        node *cur = trie;
        for (int j = 0; j < s.size(); j++) {
            if (cur->adj.count(s[j])) {
                cur = cur->adj[s[j]];
            }
            else {
                cur = cur->adj[s[j]] = new node();
                gc.push_back(cur);
            }
        }
        cur->end = true;
    }

    res = vector<char>();
    solve();
    while (res.back() != 'P') res.pop_back();
    cout << res.size() << '\n';
    for (auto &e : res) cout << e << '\n';

    for (auto &e : gc) delete e;
    return 0;
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int j = 0; j < s.size(); j++) {
      |                         ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1884 KB Output is correct
2 Correct 4 ms 2136 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5848 KB Output is correct
2 Correct 19 ms 12384 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 14548 KB Output is correct
2 Correct 9 ms 3420 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 36544 KB Output is correct
2 Correct 192 ms 85848 KB Output is correct
3 Correct 104 ms 42688 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 27588 KB Output is correct
2 Correct 177 ms 101304 KB Output is correct
3 Correct 108 ms 48576 KB Output is correct
4 Correct 196 ms 95736 KB Output is correct