제출 #1275470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275470		papaulo	Type Printer (IOI08_printer)	C++20	100 / 100	102 ms	59868 KiB

printer

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

#define MAXI 500500

vector<char> ans;
int trie[MAXI][26];
int has[MAXI];
int len[MAXI];
int mlen[MAXI];
int id=0;

void insert(string s) {
    int n=0;
    for(char c : s) {
        int &t=trie[n][c-'a'];
        if(!t) {
            t=++id;
        }
        len[t]=len[n]+1;
        n=t;
    }
    has[n]=1;
}

void dfs1(int v) {
    mlen[v]=len[v];
    for(int i=0;i<26;i++) {
        int u=trie[v][i];
        if(!u) continue;
        dfs1(u);
        mlen[v]=max(mlen[v], mlen[u]);
    }
}

void dfs2(int v) {
    if(has[v]) ans.push_back('P');
    for(int i=0;i<26;i++) {
        int u=trie[v][i];
        if(!u||mlen[u]==mlen[v]) continue;
        ans.push_back('a'+i);
        dfs2(u);
        ans.push_back('-');
    }
    for(int i=0;i<26;i++) {
        int u=trie[v][i];
        if(!u||mlen[u]<mlen[v]) continue;
        ans.push_back('a'+i);
        dfs2(u);
        ans.push_back('-');
    }
}

int main() {
    memset(trie, 0, sizeof(trie));
    memset(has, 0, sizeof(has));
    memset(len, 0, sizeof(len));
    memset(mlen, 0, sizeof(mlen));
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    while(n--) {
        string s;
        cin >> s;
        insert(s);
    }
    dfs1(0);
    dfs2(0);
    for(int i=0;i<mlen[0];i++) ans.pop_back();
    cout << ans.size() << endl;
    for(char c : ans) cout << c << "\n";
}

• 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