oj.uz

Submission #54717

# Submission time Handle Problem Language Result Execution time Memory
54717 2018-07-04T18:27:39 Z updown1 Type Printer (IOI08_printer) C++17
100 / 100
 233 ms 73968 KB 
/*
Use a trie to store the words
Answer by traversing the trie
longest word last so it doesn't have to be deleted
need to optimize memory a little bit
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
//500,000,000 operations
const int MAXN = 25000, MAXM = 500001;//, INF = 1000000000000000000;
//Global Variables
int N, M = 1;
pair<short, string> inp[MAXN];
vector<char> out;

struct trie {
    int go[26];
    bool big[26];
    bool word;
    trie() {
        For (i, 0, 26) go[i] = -1, big[i] = false;
        word = false;
    }
};
vector<trie> tree;
void add(string a, int tnode, int aloc) {
    if (aloc == a.length()) {
        tree[tnode].word = true;
        return;
    }
    int nex = a[aloc]-'a';
    if (tree[tnode].go[nex] == -1) {
        tree[tnode].go[nex] = M;
        tree.pb(trie());
        M++;
    }
    add(a, tree[tnode].go[nex], aloc+1);
}

void addbig(string a, int tnode, int aloc) {
    if (aloc == a.length()) {
        tree[tnode].word = true;
        return;
    }
    int nex = a[aloc]-'a';
    if (tree[tnode].go[nex] == -1) {
        tree[tnode].go[nex] = M;
        tree.pb(trie());
        M++;
    }
    tree[tnode].big[nex] = true;
    addbig(a, tree[tnode].go[nex], aloc+1);
}
void traverse (int tnode) {
    trie at = tree[tnode];
    if (at.word) out.pb('P');
    For (i, 0, 26) if (at.go[i] != -1 && !at.big[i]) {
        out.pb((char)(i+'a'));
        traverse(at.go[i]);
        out.pb('-');
    }
    For (i, 0, 26) if (at.go[i] != -1 && at.big[i]) {
        out.pb((char)(i+'a'));
        traverse(at.go[i]);
        out.pb('-');
    }
}

main() {
    //ifstream cin("test.in");
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    ffi {cin >> inp[i].b; inp[i].a = inp[i].b.length();}
    sort(inp, inp+N);
    tree.pb(trie());
    ffi {
        if (i == N-1) addbig(inp[i].b, 0, 0);
        else add(inp[i].b, 0, 0);
    }
    traverse(0);
    while (out.back() == '-') out.pop_back();
    w<< out.size()<<e;
    for (char i: out) w<< i<<e;
}

Compilation message

printer.cpp: In function 'void add(std::__cxx11::string, int, int)':
printer.cpp:41:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (aloc == a.length()) {
         ~~~~~^~~~~~~~~~~~~
printer.cpp: In function 'void addbig(std::__cxx11::string, int, int)':
printer.cpp:55:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (aloc == a.length()) {
         ~~~~~^~~~~~~~~~~~~
printer.cpp: At global scope:
printer.cpp:83:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2872 KB Output is correct
2 Correct 8 ms 4156 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6252 KB Output is correct
2 Correct 30 ms 10540 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 10884 KB Output is correct
2 Correct 25 ms 10884 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 36572 KB Output is correct
2 Correct 207 ms 71572 KB Output is correct
3 Correct 119 ms 71572 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 71572 KB Output is correct
2 Correct 233 ms 72884 KB Output is correct
3 Correct 128 ms 72884 KB Output is correct
4 Correct 209 ms 73968 KB Output is correct