oj.uz

답안 #120062

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
120062 2019-06-23T07:19:13 Z dolphingarlic Type Printer (IOI08_printer) C++14
10 / 100
 72 ms 36852 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 = "";

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) {
        string s;
        cin >> s;
        if (s.length() > longest.length()) longest = s;
        else insert(root, s);
    }
    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:27:9:
     FOR(i, 0, key.length()) {
         ~~~~~~~~~~~~~~~~~~             
printer.cpp:27: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:39:9:
     FOR(i, 0, longest.length()) {
         ~~~~~~~~~~~~~~~~~~~~~~         
printer.cpp:39:5: note: in expansion of macro 'FOR'
     FOR(i, 0, longest.length()) {
     ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 384 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 384 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB didn't print every word

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 512 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1920 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 6060 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 14836 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 72 ms 36852 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 28772 KB didn't print every word
2 Halted 0 ms 0 KB -