Submission #1360103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1360103		minh201643	Type Printer (IOI08_printer)	C++20	100 / 100	105 ms	105192 KiB

printer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 500005
#define file

int n;

struct node {
    bool is_end;
    int ma, len, val;
    node* child[26];
};

node* root;

node* create_node () {
    node* res = new node ();

    res -> is_end = 0;
    for (int i = 0; i < 26; i++) res -> child[i] = NULL;
    res -> len = 0;
    res -> ma = 0;
    res -> val = 0;

    return res;
}
void add (string s) {
    node* p = root;
    for (char c : s) {
        if (p -> child[c - 'a'] == NULL) p -> child[c - 'a'] = create_node ();
        p = p -> child[c - 'a'];
    }
    p -> is_end = 1;
}

void dfs (node* u) {
    u -> val += u -> is_end;

    for (int i = 0; i < 26; i++) {
        if (u -> child[i] == NULL) continue;
        node* v = u -> child[i];

        dfs (v);

        u -> len += v -> len + 2;
        u -> val += v -> val;
        u -> ma = max (u -> ma, v -> ma + 1);
    }
}

int tg, ok = 0;
void print_1 (node* u) {
    if (u -> is_end) cout << "P\n";
    for (int i = 0; i < 26; i++) {
        if (u -> child[i] == NULL) continue;
        node* v = u -> child[i];

        if (v -> ma + 1 == tg && ok == 0) {
            ok = 1;
            tg = i;
            continue;
        }

        cout << (char)(i + 'a') << '\n';
        print_1 (v);
        cout << "-\n";
    }
}

vector<char> ans;
void print_2 (node* u) {
    if (u -> is_end) ans.push_back('P');
    vector<pair<int, int> > ve;
    for (int i = 0; i < 26; i++) {
        if (u -> child[i] == NULL) continue;
        node* v = u -> child[i];

        if (i != tg && u == root) continue;

        ve.push_back({v -> ma, i});
    }

    sort (ve.begin(), ve.end(), [](const pair<int, int>& x, const pair<int, int>& y){
          return x.first < y.first;
    });

    for (auto x : ve) {
        ans.push_back((char)(x.second + 'a'));
        print_2 (u -> child[x.second]);
        ans.push_back('-');
    }
}

void read() {
    cin >> n;
    root = create_node ();
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        add (s);
    }
}

void solve() {
    dfs (root);
    cout << root -> len - root -> ma + root -> val << '\n';

    tg = root -> ma;
    print_1 (root);
    print_2 (root);

    while (ans.size() && ans.back() == '-') ans.pop_back();
    for (char c : ans) cout << c << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    if (fopen(file".INP","r")) {
        freopen(file".INP","r",stdin);
        freopen(file".OUT","w",stdout);
    }

    read();
    solve();

    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(file".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
printer.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(file".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