oj.uz

Submission #734662

# Submission time Handle Problem Language Result Execution time Memory
734662 2023-05-02T18:48:13 Z ttamx Type Printer (IOI08_printer) C++14
100 / 100
 163 ms 111844 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=25005;

int n;  
vector<char> ans;

struct node{
    char c;
    int cnt,lv;
    array<node*,27> adj;
    node(char c,int cnt=1):c(c),cnt(cnt),adj(array<node*,27>({})){}
};
typedef node* pnode;

void insert(pnode pt,string &s,int idx){
    if(idx==s.size()){
        pnode &t=pt->adj[26];
        if(!t)return void(t=new node('P'));
        return void(t->cnt++);
    }
    pnode &t=pt->adj[s[idx]-'a'];
    if(!t)t=new node(s[idx]);
    insert(t,s,idx+1);
}

int dfs(pnode t){
    t->lv=0;
    for(auto nt:t->adj)if(nt)t->lv=max(t->lv,dfs(nt));
    t->lv++;
    return t->lv;
}

void dfs2(pnode t){
    if(t->c!='*')for(int i=0;i<t->cnt;i++)ans.emplace_back(t->c);
    bool ok=false;
    pnode mx=nullptr;
    for(auto nt:t->adj)if(nt)if(!mx||nt->lv>mx->lv)mx=nt;
    for(auto nt:t->adj)if(nt&&nt!=mx)dfs2(nt),ok=true;
    if(mx)dfs2(mx),ok=true;
    if(ok)ans.emplace_back('-');
}

pnode rt=new node('*');

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i=0;i<n;i++){
        string s;
        cin >> s;
        insert(rt,s,0);
    }
    dfs(rt);
    dfs2(rt);
    while(!ans.empty()&&ans.back()=='-')ans.pop_back();
    cout << ans.size() << "\n";
    for(auto x:ans)cout << x << "\n";
}

Compilation message

printer.cpp: In function 'void insert(pnode, std::string&, int)':
printer.cpp:19:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     if(idx==s.size()){
      |        ~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2108 KB Output is correct
2 Correct 4 ms 2644 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6996 KB Output is correct
2 Correct 32 ms 14744 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 17792 KB Output is correct
2 Correct 14 ms 6228 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 43124 KB Output is correct
2 Correct 137 ms 93940 KB Output is correct
3 Correct 86 ms 50836 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 36300 KB Output is correct
2 Correct 163 ms 111844 KB Output is correct
3 Correct 92 ms 57796 KB Output is correct
4 Correct 144 ms 105904 KB Output is correct