oj.uz

Submission #924998

# Submission time Handle Problem Language Result Execution time Memory
924998 2024-02-10T10:53:07 Z vjudge1 Type Printer (IOI08_printer) C++17
100 / 100
 118 ms 74180 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define all(x) x.begin(), x.end()
#define INF 0x3f3f3f3f
#define INFLL (ll)0x3f3f3f3f3f3f3f3f
const int MOD = 1e9 + 7, SZ = 1e5 + 10;

// Trie v0.1
struct trie{
    vector<vector<int>> Trie;
    vector<int> End;
    vector<char> ans;
    int MAXN, node_cnt;
    string big;
    trie(int N) : MAXN(N), node_cnt(0) {
        Trie.resize(MAXN, vector<int>(26));
        End.resize(MAXN);
    }
    void insert(string &word){
        int node = 0;
        for(int i = 0; i < word.size(); i++){
            if(Trie[node][word[i] - 'a'] == 0){
                Trie[node][word[i] - 'a'] = ++node_cnt;
            }
            node = Trie[node][word[i] - 'a'];
        }
        End[node]++;
    }
    void solve(int node = 0, int x = 0){
        for(int i = 0; i < End[node]; i++){
            ans.push_back('P');
        }
        for(int i = 0; i < 26; i++){
            if(x != -1 && (char)('a' + i) == big[x]) continue;
            if(Trie[node][i] == 0) continue;
            ans.push_back((char)('a' + i));
            solve(Trie[node][i], -1);
            ans.push_back('-');
        }
        if(x != -1 && x != big.size()){
            ans.push_back(big[x]);
            solve(Trie[node][big[x] - 'a'], x + 1);
        }
    }
} Trie(25000 * 20);

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, mx = 0;
    cin >> n;
    string s[n];
    for(auto &i : s){
        cin >> i;
        Trie.insert(i);
        if(mx < i.size()){
            mx = i.size();
            Trie.big = i;
        }
    }
    Trie.solve();
    cout << Trie.ans.size() << endl;
    // cout << Trie.ans.size() - mx << endl;
    for(int i = 0; i < Trie.ans.size(); i++){
        cout << Trie.ans[i] << endl;
    }
    return 0;
}
// by me

Compilation message

printer.cpp: In member function 'void trie::insert(std::string&)':
printer.cpp:23:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int i = 0; i < word.size(); i++){
      |                        ~~^~~~~~~~~~~~~
printer.cpp: In member function 'void trie::solve(int, int)':
printer.cpp:42:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if(x != -1 && x != big.size()){
      |                       ~~^~~~~~~~~~~~~
printer.cpp: In function 'int32_t main()':
printer.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         if(mx < i.size()){
      |            ~~~^~~~~~~~~~
printer.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for(int i = 0; i < Trie.ans.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 68952 KB Output is correct
2 Correct 41 ms 69100 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 68952 KB Output is correct
2 Correct 40 ms 68688 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68692 KB Output is correct
2 Correct 39 ms 68744 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 68688 KB Output is correct
2 Correct 41 ms 68688 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 68952 KB Output is correct
2 Correct 40 ms 68956 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 69188 KB Output is correct
2 Correct 40 ms 68952 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 69200 KB Output is correct
2 Correct 50 ms 69520 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 69840 KB Output is correct
2 Correct 45 ms 69716 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 70988 KB Output is correct
2 Correct 104 ms 73168 KB Output is correct
3 Correct 76 ms 72220 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 71068 KB Output is correct
2 Correct 118 ms 74180 KB Output is correct
3 Correct 83 ms 72652 KB Output is correct
4 Correct 111 ms 73924 KB Output is correct