oj.uz

Submission #1000104

# Submission time Handle Problem Language Result Execution time Memory
1000104 2024-06-16T16:40:29 Z vjudge1 Type Printer (IOI08_printer) C++17
0 / 100
 43 ms 54736 KB 
#include "bits/stdc++.h"

using namespace std;

#define int long long 

const int sz = 5e5 + 5;
const int inf = 1e18;

int trie[sz][26];
int depth[sz];
int leaf[sz];
int nxt = 0, cnt = 0;
char ch[sz];
vector<int> adj[sz];
vector<char> res;
int n;

struct Trie
{
    void add(string s) 
    {
        int root = 0;
        for(char c : s) 
        {
            int child = c - 'a';
            if (!trie[root][child]) 
            {
                trie[root][child] = ++nxt;
                adj[root].push_back(trie[root][child]);
                ch[trie[root][child]] = c;
            }
            root = trie[root][child];
            depth[root] = max(depth[root], (int)s.size() - (&c - &s.front()));
        }
        leaf[root] = true;
    }
    void dfs(int node) 
    {
        if (node) res.push_back(ch[node]);
        if (leaf[node]) res.push_back('P'), cnt++;
        for(int to : adj[node]) dfs(to);
        if (cnt != n) res.push_back('-');
    }
};

void solve() 
{
    cin >> n;
    Trie tree;
    for(int i = 1; i <= n; i++) 
    {
        string s;
        cin >> s;
        tree.add(s);
    }
    for(int i = 0; i <= nxt; i++) sort(adj[i].begin(), adj[i].end(), [&](int a, int b)
    {
        return depth[a] < depth[b];
    });
    tree.dfs(0);
    cout << res.size() << endl;
    for(char c : res) cout << c << ' ';
}

signed main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    // cin >> t;
    for(int i = 1; i <= t; i++) solve();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12888 KB Line "t p t t t y k d u y v x j b z h q u p P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12892 KB Line "l a b f a r y o s s k u g b k ... e e j z a t j m n q x c t n P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12120 KB Line "v b j x a v q c m x z b f i e ... - m q p c e a i r h d o n t P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12124 KB Line "i x o m s g e n n p d l u r n ... i c t n a a h h r g l a z o P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12892 KB Line "w u y P - - - j P u e g P - - ... - - e y n o r w r b i z a i P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 13916 KB Line "y P s x f s x x z p o q a d y ... - f v x r h g p y v t h e k P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 18616 KB Line "f P j s p p w z g a d d k z k ... - y c z s p j e j m o y w q P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 28332 KB Line "a P y m P - n d P - - r c P - ... - - h o p z b u c c s l u d P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 54736 KB Line "u P p P s r d r y u i v g l d ... - q q n z k g a u i a n l c P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 44488 KB Line "k P z P v P - w P - r P - a P ... P - - - j t e a r n h d j e P " doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -