(IOI) 2008 Day 1 p1 Type Printer

https://contest.yandex.com/ioi/contest/567/problems/A/

把Trie建出來之後開始DFS，最長鍊最後拜訪，拜訪完之後就不要回到 root (相當於留一些letter在printer裡面)

#include <bits/stdc++.h>
using namespace std;

const int SIGMA = 26;
const int N = 500006;

#define SZ(x) ((int)(x).size())

vector<char> ans;
vector<int> G[N];

int sz=1;
int ch[N][SIGMA];

bool is_end[N];

string add_str;

char id[N];

int idx(char c)
{
    return c-'a';
}

void addd(int now,int add_n)
{
    if (add_n == SZ(add_str))
    {
        is_end[now] = true;
        return;
    }
    int c = idx(add_str[add_n]);
    if (!ch[now][c]) ch[now][c] = ++sz;
    addd(ch[now][c],add_n+1);
}

void build_graph(int now)
{
    for (int i=0;SIGMA>i;i++)
    {
        if (ch[now][i])
        {
            G[now].push_back( ch[now][i] );
            id[ ch[now][i] ] = i+'a';
            build_graph(ch[now][i]);
        }
    }
}

int mx_depth[N];

void dfs(int now,int cur_depth)
{
    mx_depth[now] = cur_depth;
    for (int i:G[now])
    {
        dfs(i,cur_depth+1);
        mx_depth[now] = max(mx_depth[now],mx_depth[i]);
    }
}

int n;

int vis_tot=0;

void solve(int now)
{
    sort(G[now].begin(),G[now].end(),[](const int &a,const int &b)
     {
         return mx_depth[a] < mx_depth[b];
     });
    if (now != 1) ans.push_back(id[now]);
    vis_tot += is_end[now];
    if (is_end[now]) ans.push_back('P');
    for (int i:G[now])
    {
        solve(i);
    }
    if (vis_tot != n) ans.push_back('-');
}

int main ()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    int root = 1;
    for (int i=0;n>i;i++)
    {
        string s;
        cin >> s;
        add_str = s;
        addd(root,0);
    }
    build_graph(root);
    dfs(1,1);
    solve(1);
    cout << (int)ans.size() << '\n';
    for (char i:ans)
    {
        cout << i << '\n';
    }
}