oj.uz

Submission #546312

# Submission time Handle Problem Language Result Execution time Memory
546312 2022-04-07T08:05:09 Z krit3379 Type Printer (IOI08_printer) C++17
100 / 100
 149 ms 94396 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 25

struct node{
    int nxt[26],dep[26];
    bool is_end;
}t[1000000];

struct A{
    int nxt,dep;
    char c;
    bool operator<(const A& o)const{
        return dep<o.dep;
    }
};

int sz;
char s[N];
vector<char> ans;

void add(int n){
    int i,now=0;
    for(i=1;i<=n;i++){
        int idx=s[i]-'a';
        if(!t[now].nxt[idx])t[now].nxt[idx]=++sz;
        t[now].dep[idx]=max(t[now].dep[idx],n);
        now=t[now].nxt[idx];
    }
    t[now].is_end=true;
}

void dfs(int now){
    if(t[now].is_end)ans.push_back('P');
    vector<A> temp;
    for(int i=0;i<26;i++){
        if(t[now].nxt[i]){
            temp.push_back({t[now].nxt[i],t[now].dep[i],'a'+i});
        }
    }
    sort(temp.begin(),temp.end());
    for(auto [nxt,dep,c]:temp){
        ans.push_back(c);
        dfs(nxt);
        ans.push_back('-');
    }
}

int main(){
    int n,i;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf(" %s",s+1);
        add(strlen(s+1));
    }
    dfs(0);
    while(ans.back()=='-')ans.pop_back();
    printf("%d\n",ans.size());
    for(auto x:ans)printf("%c\n",x);
    return 0;
}

Compilation message

printer.cpp: In function 'void dfs(int)':
printer.cpp:38:60: warning: narrowing conversion of '(97 + i)' from 'int' to 'char' [-Wnarrowing]
   38 |             temp.push_back({t[now].nxt[i],t[now].dep[i],'a'+i});
      |                                                         ~~~^~
printer.cpp: In function 'int main()':
printer.cpp:58:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wformat=]
   58 |     printf("%d\n",ans.size());
      |             ~^    ~~~~~~~~~~
      |              |            |
      |              int          std::vector<char>::size_type {aka long unsigned int}
      |             %ld
printer.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
printer.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf(" %s",s+1);
      |         ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 980 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1748 KB Output is correct
2 Correct 4 ms 2132 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 14024 KB Output is correct
2 Correct 8 ms 3156 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 34728 KB Output is correct
2 Correct 126 ms 79312 KB Output is correct
3 Correct 63 ms 40900 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 27204 KB Output is correct
2 Correct 149 ms 94396 KB Output is correct
3 Correct 75 ms 46528 KB Output is correct
4 Correct 141 ms 89152 KB Output is correct