Submission #462604

#	Time	Username	Problem	Language	Result	Execution time	Memory
462604		JovanB	Type Printer (IOI08_printer)	C++17	100 / 100	192 ms	52128 KiB

printer

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