Submission #155621

#	Time	Username	Problem	Language	Result	Execution time	Memory
155621		karma	Type Printer (IOI08_printer)	C++14	100 / 100	201 ms	100660 KiB

printer

#include<bits/stdc++.h>
#define Task     "test"
#define pb       emplace_back

using namespace std;

const int N = 25001;
const int nAlpha = 26;

string s[N];
int n, res, Max;
struct TNode {
    int finish;
    TNode* chil[nAlpha];
} *root;
typedef TNode* PNode;

PNode Add() {
     ++res;
     PNode ptr = new TNode();
     ptr -> finish = 0;
     for(int i = 0; i < nAlpha; ++i) ptr -> chil[i] = NULL;
     return ptr;
}

void Ins(string s) {
     PNode ptr = root;
     for(int i = 0; i < int(s.size()); ++i) {
        s[i] -= 'a';
        if(ptr -> chil[s[i]] == NULL) ptr -> chil[s[i]] = Add();
        ptr = ptr -> chil[s[i]];
     }
     ++ptr -> finish;
}

void Trace(PNode ptr, int depth, bool keep, char letter) {
    if(ptr != root) cout << letter << '\n';
    for(int i = 0; i < nAlpha; ++i) {
        if(ptr -> chil[i] == NULL) continue;
        if(!keep) Trace(ptr -> chil[i], depth + 1, 0, char('a' + i));
        else if(i != s[Max][depth] - 'a') Trace(ptr -> chil[i], depth + 1, 0, char('a' + i));
    }
    if(ptr -> finish) cout << "P\n";
    if(keep && depth < int(s[Max].size())) {
        if(ptr -> chil[s[Max][depth] - 'a']) Trace(ptr -> chil[s[Max][depth] - 'a'], depth + 1, 1, s[Max][depth]);
    }
    if(!keep) cout << "-\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n; s[Max = 0] = "";
    res = -1; root = Add();
    for(int i = 1; i <= n; ++i) {
       cin >> s[i]; Ins(s[i]);
       if(int(s[Max].size()) < int(s[i].size())) Max = i;
    }
    res = res * 2 + n - s[Max].size();
    cout << res << '\n';
    Trace(root, 0, 1, 'a');
}

Compilation message (stderr)

printer.cpp: In function 'void Ins(std::__cxx11::string)':
printer.cpp:30:28: warning: array subscript has type 'char' [-Wchar-subscripts]
         if(ptr -> chil[s[i]] == NULL) ptr -> chil[s[i]] = Add();
                            ^
printer.cpp:30:55: warning: array subscript has type 'char' [-Wchar-subscripts]
         if(ptr -> chil[s[i]] == NULL) ptr -> chil[s[i]] = Add();
                                                       ^
printer.cpp:31:31: warning: array subscript has type 'char' [-Wchar-subscripts]
         ptr = ptr -> chil[s[i]];
                               ^
printer.cpp: In function 'int main()':
printer.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(Task".out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10