oj.uz

Submission #120064

# Submission time Handle Problem Language Result Execution time Memory
120064 2019-06-23T07:21:41 Z dolphingarlic Type Printer (IOI08_printer) C++14
100 / 100
 198 ms 101760 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define FOR(i, x, y) for(int i = x; i < y; i++)
#define ALPHABET 26
typedef long long ll;
using namespace std;

vector<char> ops;
string longest = "", words[25000];

bool cmp(string a, string b) {
    return (a.length() < b.length());
}

struct TrieNode {
    TrieNode *children[ALPHABET];
    bool isEndOfWord, containsLongest;
};

TrieNode *getNode() {
    TrieNode *pNode = new TrieNode;
    pNode->isEndOfWord = false;
    pNode->containsLongest = false;
    FOR(i, 0, ALPHABET) pNode->children[i] = NULL;
    return pNode;
}

void insert(TrieNode *root, string key) {
    TrieNode *pCrawl = root;

    FOR(i, 0, key.length()) {
        int indx = key[i] - 'a';
        if (!pCrawl->children[indx]) pCrawl->children[indx] = getNode();
        pCrawl = pCrawl->children[indx];
    }
    pCrawl->isEndOfWord = true;
}

void insertLongest(TrieNode *root) {
    TrieNode *pCrawl = root;
    pCrawl->containsLongest = true;

    FOR(i, 0, longest.length()) {
        int indx = longest[i] - 'a';
        if (!pCrawl->children[indx]) pCrawl->children[indx] = getNode();
        pCrawl = pCrawl->children[indx];
        pCrawl->containsLongest = true;
    }
    pCrawl->isEndOfWord = true;
}

void dfs(TrieNode *root) {
    if (root->isEndOfWord) ops.push_back('P');
    if (root->containsLongest) {
        FOR(i, 0, ALPHABET) {
            if (root->children[i] && !(root->children[i]->containsLongest)) {
                ops.push_back(i + 'a');
                dfs(root->children[i]);
                ops.push_back('-');
            }
        }
        FOR(i, 0, ALPHABET) {
            if (root->children[i] && root->children[i]->containsLongest) {
                ops.push_back(i + 'a');
                dfs(root->children[i]);
            }
        }
    } else {
        FOR(i, 0, ALPHABET) {
            if (root->children[i]) {
                ops.push_back(i + 'a');
                dfs(root->children[i]);
                ops.push_back('-');
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;

    TrieNode *root = getNode();
    FOR(i, 0, n) {
        cin >> words[i];
    }
    sort(words, words + n, cmp);
    FOR(i, 0, n - 1) {
        insert(root, words[i]);
    }
    longest = words[n - 1];
    insertLongest(root);

    dfs(root);
    cout << ops.size() << '\n';
    for (char i : ops) cout << i << '\n';
    return 0;
}

Compilation message

printer.cpp: In function 'void insert(TrieNode*, std::__cxx11::string)':
printer.cpp:3:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for(int i = x; i < y; i++)
printer.cpp:31:9:
     FOR(i, 0, key.length()) {
         ~~~~~~~~~~~~~~~~~~             
printer.cpp:31:5: note: in expansion of macro 'FOR'
     FOR(i, 0, key.length()) {
     ^~~
printer.cpp: In function 'void insertLongest(TrieNode*)':
printer.cpp:3:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for(int i = x; i < y; i++)
printer.cpp:43:9:
     FOR(i, 0, longest.length()) {
         ~~~~~~~~~~~~~~~~~~~~~~         
printer.cpp:43:5: note: in expansion of macro 'FOR'
     FOR(i, 0, longest.length()) {
     ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2660 KB Output is correct
2 Correct 6 ms 3072 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6860 KB Output is correct
2 Correct 26 ms 13432 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 15608 KB Output is correct
2 Correct 17 ms 4352 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 37492 KB Output is correct
2 Correct 176 ms 85560 KB Output is correct
3 Correct 103 ms 45056 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 29272 KB Output is correct
2 Correct 198 ms 101760 KB Output is correct
3 Correct 114 ms 51056 KB Output is correct
4 Correct 184 ms 95984 KB Output is correct