Submission #1083464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083464		raul2008487	Type Printer (IOI08_printer)	C++17	100 / 100	106 ms	106580 KiB

printer

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define in insert
#define fi first
#define se second
#define endl "\n"
#define vl vector<ll>
#define all(v) v.begin(), v.end()

using namespace std;
const ll inf = 1e17;
const int sz = 5e5 + 123;
const int MAX = 2001;
const ll mod = 1e9;
ll id, to[sz][26], par[sz], d[sz], noe;
vl cnt(sz), sub(sz);
char alphabet[26];
bool longest[sz];
array<ll, 2> best = {0, 0};
void insert(string &s){
    ll p = 0;
    sub[0] ++;
    for(auto c: s){
        if(!to[p][c - 'a']){
            to[p][c - 'a'] = ++id;
            par[id] = p;
            d[id] = d[p] + 1;
            if(d[id] > best[0]){
                best = {d[id], id};
            }
        }
        p = to[p][c - 'a'];
        sub[p] ++;
    }
    cnt[p] ++;
}
void dfs(ll p){
    while(cnt[p]--){
        cout << 'P' << endl;
    }
    char l = '*';
    ll nxt;
    for(char c: alphabet){
        nxt = to[p][c - 'a'];
        if(!nxt){continue;}
        if(longest[nxt]){
            l = c;
        }
        else{
            cout << c << endl;
            dfs(nxt);
            cout << '-' << endl;
        }
    }
    if(l != '*'){
        cout << l << endl;
        dfs(to[p][l - 'a']);
    }
}
void solve(){
    ll n, i, j;
    for(i = 0; i < 26; i++){
        alphabet[i] = char('a' + i);
    }
    cin >> n;
    string s;
    for(i = 1; i <= n; i++){
        cin >> s;
        insert(s);
    }
    ll node = best[1];
    noe  = id * 2;
    // cout << noe << endl;
    while(node){
        longest[node] = 1;
        noe --;
        node = par[node];
    }
    cout << noe + n << endl;
    dfs(0);


}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}
/*
5
pushkin
lermontov
tolstoy
gogol
gorkiy
*/

Compilation message (stderr)

printer.cpp: In function 'void solve()':
printer.cpp:63:14: warning: unused variable 'j' [-Wunused-variable]
   63 |     ll n, i, j;
      |              ^

• 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