Submission #953207

#	Time	Username	Problem	Language	Result	Execution time	Memory
953207		AverageAmogusEnjoyer	Type Printer (IOI08_printer)	C++17	100 / 100	88 ms	60168 KiB

printer

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i,T j) { return i > j ? i = j, true : false; }
template<class T> bool cmax(T &i,T j) { return i < j ? i = j, true : false; }

constexpr int nax = 1e6;
int trie[nax][26];
bool is_longest[nax];
int ending[nax];
string ans;
int par[nax];
int depth[nax];
void dfs(int x) {
    while(ending[x]--) {
        ans+="P";
    }
    for (int i=0;i<26;i++) {
        if (!trie[x][i]||is_longest[trie[x][i]]) { continue; } 
        ans+=char(i+'a');
        dfs(trie[x][i]);
    }
    for (int i=0;i<26;i++) {
        if (trie[x][i]&&is_longest[trie[x][i]]) {
            ans+=char(i+'a');
            dfs(trie[x][i]);
        }
    }
    if (!is_longest[x]) {
        ans+="-";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    int cnt=1;
    par[0]=-1;
    while(n--) {
        string s;
        cin >> s;
        int x=0;
        for (auto &c: s) {
            if (!trie[x][c-'a']) { 
                trie[x][c-'a']=cnt;
                par[cnt]=x;
                depth[cnt]=depth[x]+1;
                cnt++;
            }
            x=trie[x][c-'a'];
        }
        ending[x]++;
    }
    int x=(int)(max_element(depth,depth+nax)-depth);
    while(x != -1) {
        is_longest[x]=true;
        x=par[x];
    }
    dfs(0);
    cout << ans.size() << "\n";
    for (auto &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