oj.uz

Submission #935210

# Submission time Handle Problem Language Result Execution time Memory
935210 2024-02-28T20:07:53 Z asdasdqwer Type Printer (IOI08_printer) C++14
20 / 100
 380 ms 225520 KB 
#include <bits/stdc++.h>
using namespace std;

struct Node {
    char l;
    map<char,int> child;
};

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

void insWord(string &s) {
    int idx = 0;
    for (auto &x:s) {
        if (trie[idx].child[x-'a'] == 0) {
            trie[idx].child[x-'a'] = last;
            trie[last].l = x;
            last++;
        }
        idx = trie[idx].child[x-'a'];
    }
}

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

vector<Operation> out;

void traversal(int index) {
    bool foundOne = false;
    for (int i=0;i<26;i++) {
        if (trie[index].child[i] == 0) continue;
        Operation op;op.chr = i + 'a';
        out.push_back(op);
        traversal(trie[index].child[i]);
        op.isBack = true;
        out.push_back(op);
        foundOne = true;
    }

    if (!foundOne) {
        Operation op;op.isPrint=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);
    }

    // it's always optimal to stop at the word with the largest length
    string s = "";
    for (auto &x:v) {
        if (x.size() > s.size()) {
            s = x;
        }
    }

    int index = 0;
    for (auto &x:s) {
        int nxt;
        for (int i=0;i<26;i++) {
            if (trie[index].child[i] != 0 && i != (x-'a')) {
                Operation op;op.chr=i+'a';
                out.push_back(op);
                traversal(trie[index].child[i]);
                op.isBack = true;
                out.push_back(op);
            }

            else if (i == (x-'a')) {
                nxt = trie[index].child[i];
            }
        }

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

    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 'int main()':
printer.cpp:75:27: warning: 'nxt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |             if (trie[index].child[i] != 0 && i != (x-'a')) {
      |                           ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 27740 KB Output is correct
2 Correct 6 ms 27864 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 27740 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27868 KB Output is correct
2 Incorrect 8 ms 27740 KB didn't print every word
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 28508 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 35932 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 58452 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 105992 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 380 ms 225520 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 313 ms 181776 KB didn't print every word
2 Halted 0 ms 0 KB -