Submission #1308795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308795		nvc2k8	Type Printer (IOI08_printer)	C++20	100 / 100	114 ms	100072 KiB

printer

#include <bits/stdc++.h>
#define TASK "printer"
#define endl mmm
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define all(C) (C).begin(), (C).end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int INT_LIM = 2147483647;
const ll LL_LIM = 9223372036854775807;
template <typename X> bool minimize(X &x, const X &y) {if (x>y){x = y; return true;}return false;}
template <typename X> bool maximize(X &x, const X &y) {if (x<y){x = y; return true;}return false;}
///------------------------------------------///
int n;

struct trie{
    struct node{
        node *child[26];
        int deep;
        bool leaf;
        node ()
        {
            deep = 0;
            leaf = 0;
            FOR(i, 0, 25) child[i] = NULL;
        }
    };
    int numnode = 0;
    node *root = new node();

    void init()
    {
        root = new node();
        numnode = 0;
    }
    void insertWord(string &x)
    {
        node *cur = root;
        for (auto c:x)
        {
            if (!cur->child[c-'a'])
            {
                cur->child[c-'a'] = new node();
                numnode++;
            }
            cur = cur->child[c-'a'];
        }
        cur->leaf = true;
    }

    void calcDeep(node *cur)
    {
        FOR(c, 0, 25) if (cur->child[c])
        {
            calcDeep(cur->child[c]);
            maximize(cur->deep, cur->child[c]->deep+1);
        }
    }
    void traverse(node *cur)
    {
        if (cur->leaf)
        {
            cout << "P" << '\n';
            n--;
        }
        if (!n) exit(0);
        int big = -1;
        FOR(c, 0, 25) if (cur->child[c])
        {
            if (big==-1 || cur->child[c]->deep > cur->child[big]->deep) big = c;
        }

        FOR(c, 0, 25) if (cur->child[c] && c!=big)
        {
            cout << char(c+'a') << '\n';
            traverse(cur->child[c]);
        }
        if (big!=-1)
        {
            cout << char(big+'a') << '\n';
            traverse(cur->child[big]);
        }

        cout << '-' << '\n';
    }
} trie;

string a[26005];

void inp()
{
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
}

void solve()
{
    trie.init();
    FOR(i, 1, n)
    {
        trie.insertWord(a[i]);
    }

    trie.calcDeep(trie.root);
    cout << trie.numnode*2-trie.root->deep+n << '\n';
    trie.traverse(trie.root);
}

signed main()
{
    ///--------------------------///
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    if (fopen(TASK".INP","r")!=NULL)
    {
        freopen(TASK".INP","r",stdin);
        freopen(TASK".OUT","w",stdout);
    }
    ///--------------------------///

    int NTEST = 1;
    bool multitest = 0;
    if (multitest) cin >> NTEST;

    while (NTEST--)
    {
        inp();
        solve();
    }

    return 0;
}

///------------------------------------------///

Compilation message (stderr)

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