Submission #734662

#	Time	Username	Problem	Language	Result	Execution time	Memory
734662		ttamx	Type Printer (IOI08_printer)	C++14	100 / 100	163 ms	111844 KiB

printer

#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 (stderr)

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 / 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