oj.uz

Submission #498326

# Submission time Handle Problem Language Result Execution time Memory
498326 2021-12-25T04:09:05 Z Fake4Fun Type Printer (IOI08_printer) C++14
100 / 100
 101 ms 48632 KB 
//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

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3280 KB Output is correct
2 Correct 13 ms 6352 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7496 KB Output is correct
2 Correct 6 ms 2000 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 18076 KB Output is correct
2 Correct 84 ms 40972 KB Output is correct
3 Correct 49 ms 21340 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14280 KB Output is correct
2 Correct 101 ms 48632 KB Output is correct
3 Correct 56 ms 24216 KB Output is correct
4 Correct 80 ms 45908 KB Output is correct