oj.uz

Submission #935220

# Submission time Handle Problem Language Result Execution time Memory
935220 2024-02-28T20:45:55 Z asdasdqwer Type Printer (IOI08_printer) C++14
100 / 100
 92 ms 59328 KB 
#include <bits/stdc++.h>
using namespace std;

struct Node {
    char l;
    map<char,int> child;
    bool isEnd = false;
};

vector<Node> trie(500001);
int last = 1;

void insWord(string &s) {
    int idx = 0;
    for (auto &x:s) {
        if (trie[idx].child.find(x) == trie[idx].child.end()) {
            trie[idx].child[x] = last;
            trie[last].l = x;
            last++;
        }
        idx = trie[idx].child[x];
    }
    trie[idx].isEnd = true;
}

struct Operation {
    char chr;
    bool isPrint = false;
    bool isBack = false;
};

vector<Operation> out;

void traversal(int index) {
    if (trie[index].isEnd) {
        Operation op;op.isPrint=true;
        out.push_back(op);
    }

    for (auto [chr, idx]:trie[index].child) {
        Operation op;op.chr = chr;
        out.push_back(op);
        traversal(idx);
        op.isBack = true;
        out.push_back(op);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;cin>>n;
    vector<string> v(n);
    for (auto &x:v)cin>>x;
    trie[0].l = ' ';

    for (auto x:v) {
        insWord(x);
    }

    string s = "";
    for (auto &x:v) {
        if (x.size() > s.size()) {
            s = x;
        }
    }

    int index = 0;

    for (auto &x:s) {
        int nxt;
        for (auto [chr, idx] : trie[index].child) {
            if (chr != x) {
                Operation op;op.chr=chr;
                out.push_back(op);
                traversal(idx);
                op.isBack = true;
                out.push_back(op);
            }

            else {
                nxt = idx;
            }
        }

        Operation op;op.chr=x;
        out.push_back(op);
        index = nxt;

        if (trie[index].isEnd) {
            Operation op;op.isPrint=true;
            out.push_back(op);
        }
    }

    cout<<out.size()<<"\n";
    for (auto &x:out) {
        if (x.isBack) {
            cout<<"-\n";
        }

        else if (x.isPrint) {
            cout<<"P\n";
        }

        else {
            cout<<x.chr<<"\n";
        }
    }
}

Compilation message

printer.cpp: In function 'void traversal(int)':
printer.cpp:40:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for (auto [chr, idx]:trie[index].child) {
      |               ^
printer.cpp: In function 'int main()':
printer.cpp:73:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |         for (auto [chr, idx] : trie[index].child) {
      |                   ^
printer.cpp:91:23: warning: 'nxt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   91 |         if (trie[index].isEnd) {
      |                       ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31576 KB Output is correct
2 Correct 8 ms 31580 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31672 KB Output is correct
2 Correct 7 ms 31580 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31576 KB Output is correct
2 Correct 7 ms 31580 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 32092 KB Output is correct
2 Correct 9 ms 32348 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 33312 KB Output is correct
2 Correct 16 ms 35156 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 35932 KB Output is correct
2 Correct 13 ms 33308 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 41780 KB Output is correct
2 Correct 81 ms 55740 KB Output is correct
3 Correct 56 ms 44744 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 39896 KB Output is correct
2 Correct 92 ms 59328 KB Output is correct
3 Correct 53 ms 46464 KB Output is correct
4 Correct 70 ms 57792 KB Output is correct