oj.uz

Submission #546213

# Submission time Handle Problem Language Result Execution time Memory
546213 2022-04-06T16:23:10 Z perchuts Type Printer (IOI08_printer) C++17
100 / 100
 157 ms 105916 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e5+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

struct trie{
    trie *alpha[27], *parent;
    bool later, isEnd;
    trie(trie *p){
        for(int i=0;i<27;++i)alpha[i] = nullptr;
        later = 0, parent = p, isEnd = 0;
    }
}*Trie;

int mx;
trie *deepest;
void dfs(trie *cur, int height){
    if(ckmax(mx,height))deepest = cur;
    for(int i=0;i<26;++i){
        if(cur->alpha[i]!=nullptr){
            dfs(cur->alpha[i],height+1);
        }
    }
}
vector<char>ans;

void dfs2(trie *cur){
    int last = -1;
    if(cur->isEnd==1)ans.pb('P');
    for(int i=0;i<26;++i){
        if(cur->alpha[i]!=nullptr){
            if(cur->alpha[i]->later==1)last = i;
            else{
                ans.pb(char('a'+i));
                dfs2(cur->alpha[i]);
            }
        }
    }
    if(last!=-1){
        ans.pb(char('a'+last));
        dfs2(cur->alpha[last]);
    }
    if(cur->later==0)ans.pb('-');
}

int main(){_
    int n;cin>>n;
    Trie = new trie(nullptr);
    for(int i=1;i<=n;++i){
        string s;cin>>s;
        trie *cur = Trie;
        for(auto x:s){
            int ch = x - 'a';
            if(cur->alpha[ch]==nullptr)cur->alpha[ch] = new trie(cur);
            cur = cur->alpha[ch];
        }
        cur->isEnd = 1;
    }
    dfs(Trie, 1);
    while(deepest!=nullptr){
        deepest->later = 1, deepest = deepest->parent;
    }
    dfs2(Trie);
    cout<<sz(ans)<<endl;
    for(auto x:ans)cout<<x<<endl;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1876 KB Output is correct
2 Correct 3 ms 2388 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6356 KB Output is correct
2 Correct 24 ms 13332 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15692 KB Output is correct
2 Correct 8 ms 3412 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 38852 KB Output is correct
2 Correct 116 ms 89040 KB Output is correct
3 Correct 65 ms 45668 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 30404 KB Output is correct
2 Correct 157 ms 105916 KB Output is correct
3 Correct 77 ms 51920 KB Output is correct
4 Correct 116 ms 99976 KB Output is correct