oj.uz

Submission #462604

# Submission time Handle Problem Language Result Execution time Memory
462604 2021-08-10T23:35:11 Z JovanB Type Printer (IOI08_printer) C++17
100 / 100
 192 ms 52128 KB 
#include <bits/stdc++.h>
using namespace std;

queue <char> q;

int cnt=0;
char letter[500005];
int nxt[500005][26];
bool mark[500005];
int kraj[500005];

void addtrie(string s, int k){
    int v = 0;
    int x = s.size();
    for(int i=0; i<x; i++){
        int ch = s[i]-'a';
        if(!nxt[v][ch]) nxt[v][ch] = ++cnt;
        v = nxt[v][ch];
        letter[v] = ch+'a';
        if(k == 1) mark[v] = 1;
    }
    kraj[v] = 1;
}

void dfs(int v){
    if(v) q.push(letter[v]);
    if(kraj[v]){q.push('P'); kraj[v] = 0;}
    for(int i=0; i<26; i++){
        if(nxt[v][i] && !mark[nxt[v][i]]) dfs(nxt[v][i]);
    }
    for(int i=0; i<26; i++){
        if(nxt[v][i] && mark[nxt[v][i]]) dfs(nxt[v][i]);
    }
    if(!mark[v] && v) q.push('-');
}

bool cmp(string a, string b){
    return a.size() < b.size();
}

string str[25005];

int main(){

    int n;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> str[i];
    sort(str+1, str+1+n, cmp);
    for(int i=1; i<n; i++){
        addtrie(str[i], 0);
    }
    addtrie(str[n], 1);
    dfs(0);
    cout << q.size() << "\n";
    while(!q.empty()){
        cout << q.front() << "\n";
        q.pop();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1868 KB Output is correct
2 Correct 5 ms 1996 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3864 KB Output is correct
2 Correct 26 ms 7236 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 8264 KB Output is correct
2 Correct 20 ms 2764 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 19500 KB Output is correct
2 Correct 164 ms 43924 KB Output is correct
3 Correct 100 ms 22852 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 15300 KB Output is correct
2 Correct 192 ms 52128 KB Output is correct
3 Correct 120 ms 25784 KB Output is correct
4 Correct 182 ms 49412 KB Output is correct