Submission #918952

#	Time	Username	Problem	Language	Result	Execution time	Memory
918952		biank	Type Printer (IOI08_printer)	C++14	100 / 100	89 ms	51064 KiB

printer

#include <bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define SIZE(x) (int)x.size()
#define forn(i,n) for(int i=0;i<int(n);i++)
typedef long long ll;
typedef vector<int> vi;

const int MAXN = 5e5+5;

int adj[MAXN][26], t=0;
bool flag1[MAXN], flag2[MAXN];

void insert(string s, bool longest) {
    int u=0;
    for(char c:s) {
        flag2[u]|=longest;
        int &v=adj[u][c-'a'];
        if(!v) v=++t;
        u=v;
    }
    flag1[u]=true, flag2[u]|=longest;
}

string ans = "";

void dfs(int u) {
    if(flag1[u]) ans+='P';
    int j=-1;
    forn(i,26) {
        int v=adj[u][i];
        if(!v) continue;
        if(flag2[v]) j=i;
        else {
            ans+=char('a'+i);
            dfs(v);
        }
    }
    if(j!=-1) {
        ans+=char('a'+j);
        dfs(adj[u][j]);
    }
    if(!flag2[u]) ans+='-';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n; cin >> n;
    vector<string> word(n);
    int j=0;
    forn(i,n) {
        cin >> word[i];
        if(SIZE(word[j])<SIZE(word[i])) j=i;
    }
    forn(i,n) insert(word[i], i==j);
    
    dfs(0);
    cout << SIZE(ans) << '\n';
    forn(i,SIZE(ans)) cout << ans[i] << '\n';
    
    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