oj.uz

Submission #155621

# Submission time Handle Problem Language Result Execution time Memory
155621 2019-09-29T09:46:06 Z karma Type Printer (IOI08_printer) C++14
100 / 100
 201 ms 100660 KB 
#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

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6648 KB Output is correct
2 Correct 31 ms 13176 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 15224 KB Output is correct
2 Correct 14 ms 4216 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 36984 KB Output is correct
2 Correct 156 ms 84696 KB Output is correct
3 Correct 86 ms 44536 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 28920 KB Output is correct
2 Correct 201 ms 100660 KB Output is correct
3 Correct 99 ms 50508 KB Output is correct
4 Correct 188 ms 95096 KB Output is correct