Submission #1180330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180330		peteza	Type Printer (IOI08_printer)	C++17	100 / 100	78 ms	60608 KiB

printer

#include <bits/stdc++.h>
using namespace std;
const int mxn = 525005;

int n;
vector<string> vec;
string best;
int cnodeval[mxn];
int trie[mxn][26];
int nnode = 1;
int zer = 0;
vector<char> ans;

bool instrie(string &toins, int &cnode, int cidx) {
    if(cidx >= toins.size()) {
        if(cnode == -1) cnode = nnode++;
        cnodeval[cnode]++;
        return false;
    }
    if(cnode == -1) cnode = nnode++;
    if(!instrie(toins, trie[cnode][toins[cidx]-'a'], cidx+1)); //cnodeval[cnode]++;
    return true;
}

void dfs(int cur) {
    if(cnodeval[cur]) ans.push_back('P');
    for(int i=0;i<26;i++) {
        if(trie[cur][i] != -1) {
            ans.push_back(i+'a');
            dfs(trie[cur][i]);
            ans.push_back('-');
        };
    }
}

void travel(int cur, string &last, int cidx) {
    if(cnodeval[cur]) ans.push_back('P');
    if(last.size() <= cidx) return ;
    for(int i=0;i<26;i++) {
        if(trie[cur][i] != -1 && i+'a' != last[cidx]) {
            ans.push_back(i+'a');
            dfs(trie[cur][i]);
            ans.push_back('-');
        }
    }
    ans.push_back(last[cidx]);
    travel(trie[cur][last[cidx]-'a'], last, cidx+1);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    vec.resize(n);
    memset(trie, -1, sizeof trie);
    memset(cnodeval, 0, sizeof cnodeval);
    //cnodeval[0] = 1;
    for(int i=0;i<n;i++) {
        cin >> vec[i];
        if(best.size() < vec[i].size()) best = vec[i];
        bool res = instrie(vec[i], zer, 0);
    }
    travel(zer, best, 0);
    cout << ans.size() << '\n';
    for(auto &e:ans) cout << e << '\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