oj.uz

Submission #287382

# Submission time Handle Problem Language Result Execution time Memory
287382 2020-08-31T16:34:45 Z Namnamseo Type Printer (IOI08_printer) C++17
100 / 100
 152 ms 99576 KB 
#include <cstdio>

int max(int a,int b){ return a>b?a:b; }

struct node {
    node *nxt[26];
    bool term;
    int deepest;
    node(){ term=0; int i; for(i=0;i<26;++i) nxt[i]=0; deepest=0; }
    void put(char* x)
    {
        if(*x){
            if(!nxt[(*x)-'a']) nxt[(*x)-'a']=new node();
            nxt[(*x)-'a']->put(x+1);
            deepest=max(deepest,nxt[(*x)-'a']->deepest+1);
        } else term=1;
    }
};

char ans[2000010];
int top;

void dfs(node* cur)
{
    int i;
    int mi=-1;
    for(i=0;i<26;++i){
        if(cur->nxt[i]){
            if(mi==-1 || ((cur->nxt[mi]->deepest)<(cur->nxt[i]->deepest))) mi=i;
        }
    }
    if(cur->term) ans[top++]='P';
    if(mi!=-1) {
        for(i=0;i<26;++i){
            if(i==mi) continue;
            if(cur->nxt[i]){
                ans[top++]=('a'+i);
                dfs(cur->nxt[i]);
                ans[top++]='-';
            }
        }
        ans[top++]=('a'+mi);
        dfs(cur->nxt[mi]);
        ans[top++]='-';
    }
}

char buf[30];
node *root;

int main()
{
    root=new node();
    int n;
    scanf("%d",&n);
    for(;n--;){
        scanf("%s",buf);
        root->put(buf);
    }
    dfs(root);
    int i;
    while(top && ans[top-1]=='-') --top;
    printf("%d\n",top);
    for(i=0;i<top;++i){
        putchar(ans[i]); putchar(10);
    }
    return 0;
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
printer.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |         scanf("%s",buf);
      |         ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 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 512 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 1792 KB Output is correct
2 Correct 3 ms 2304 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5888 KB Output is correct
2 Correct 19 ms 12416 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14712 KB Output is correct
2 Correct 9 ms 3328 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 36600 KB Output is correct
2 Correct 127 ms 83576 KB Output is correct
3 Correct 67 ms 43128 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 28536 KB Output is correct
2 Correct 152 ms 99576 KB Output is correct
3 Correct 76 ms 48888 KB Output is correct
4 Correct 142 ms 93944 KB Output is correct