oj.uz

Submission #261913

# Submission time Handle Problem Language Result Execution time Memory
261913 2020-08-12T07:45:24 Z evpipis Type Printer (IOI08_printer) C++11
100 / 100
 185 ms 99692 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6016 KB Output is correct
2 Correct 23 ms 12544 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 14800 KB Output is correct
2 Correct 14 ms 3456 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 36720 KB Output is correct
2 Correct 160 ms 83824 KB Output is correct
3 Correct 84 ms 43248 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 28784 KB Output is correct
2 Correct 185 ms 99692 KB Output is correct
3 Correct 94 ms 49140 KB Output is correct
4 Correct 170 ms 94060 KB Output is correct