Submission #261913

#	Time	Username	Problem	Language	Result	Execution time	Memory
261913		evpipis	Type Printer (IOI08_printer)	C++11	100 / 100	185 ms	99692 KiB

printer

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
vector<char> out;

struct node{
    int wrd, dep;
    node *kid[26];

    node(){
        wrd = dep = 0;
        for (int i = 0; i < 26; i++)
            kid[i] = NULL;
    }
};

typedef node *pnode;
pnode root = new node();

void add(char str[]){
    int m = strlen(str);
    pnode cur = root;

    for (int j = 0; j < m; j++){
        cur->dep = max(cur->dep, m);

        if (cur->kid[str[j]-'a'] == NULL)
            cur->kid[str[j]-'a'] = new node();
        cur = cur->kid[str[j]-'a'];
    }

    cur->dep = max(cur->dep, m);
    cur->wrd = 1;
}

void dfs(pnode u, int keep){
    if (u->wrd)
        out.pb('P');

    pnode big = NULL;
    int pos;
    for (int j = 0; j < 26; j++){
        pnode v = u->kid[j];
        if (v == NULL) continue;

        if (big == NULL || v->dep > big->dep)
            big = v, pos = j;
    }

    for (int j = 0; j < 26; j++){
        pnode v = u->kid[j];
        if (v == NULL || v == big)
            continue;

        out.pb(j+'a'), dfs(v, 0);
    }

    if (big != NULL)
        out.pb(pos+'a'), dfs(big, keep);
    if (!keep)
        out.pb('-');
}

int main(){
    int n;
    char str[25];
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%s", str);
        add(str);
    }

    dfs(root, 1);

    printf("%d\n", (int)out.size());
    for (int i = 0; i < out.size(); i++)
        printf("%c\n", out[i]);
    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < out.size(); i++)
                     ~~^~~~~~~~~~~~
printer.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
printer.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", str);
         ~~~~~^~~~~~~~~~~
printer.cpp: In function 'void dfs(pnode, int)':
printer.cpp:60:19: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
         out.pb(pos+'a'), dfs(big, keep);
                ~~~^~~~

• 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