Submission #498326

#	Time	Username	Problem	Language	Result	Execution time	Memory
498326		Fake4Fun	Type Printer (IOI08_printer)	C++14	100 / 100	101 ms	48632 KiB

printer

//source: https://oj.uz/problem/view/IOI08_printer

#include<iostream>
#include<queue>
using namespace std;
const int N=25000, CH=26;
int n,m;
int id,nex[CH][N*CH];
bool ed[N*CH];
void add(string s){
    int c=0;
    for(auto i:s){
        int z=i-'a';
        if(!nex[z][c]) nex[z][c]=++id;
        c=nex[z][c];
    }
    ed[c]=1;
}
string op;
queue<char> q;
void DFS(int node,int depth,bool danger=0){
    int spe=(danger?op[depth]-'a':-1);
    if(ed[node]) q.push('P');
    for(int i=0;i<26;i++){
        if(!nex[i][node]||i==spe) continue;
        q.push('a'+i);
        DFS(nex[i][node],depth+1);
        q.push('-');
    }
    if(danger){
        q.push(op[depth]);
        if(depth+1==op.size()) q.push('P');
        else DFS(nex[spe][node],depth+1,1);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        string s; cin>>s;
        add(s);
        if(op.size()<s.size()) op=s;
    }
    DFS(0,0,1);
    cout<<q.size()<<'\n';
    while(!q.empty()) cout<<q.front()<<'\n', q.pop();
    return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void DFS(int, int, bool)':
printer.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         if(depth+1==op.size()) q.push('P');
      |            ~~~~~~~^~~~~~~~~~~

• 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