Submission #1214016

#TimeUsernameProblemLanguageResultExecution timeMemory
1214016leandroioileleType Printer (IOI08_printer)C++20
30 / 100
169 ms83552 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define faster ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define NMAX 25005 
#define all(x) x.begin(),x.end()
#define pb push_back
#define fi first 
#define se second
#define pic pair<int,char>

struct node{
    int tam;
    int id;
    char c;
    unordered_map<char,int>next;
    node(){
        tam=2;
        id=-1;
        c=' ';
        next.clear();
    }
};

vector<node>v;
vector<string>s;
int inicio;
string resp;

int new_node(){
    v.pb(node());
    return v.size()-1;
}

void dfs(int x){
    for(auto it:v[x].next){
        dfs(v[x].next[it.fi]);
        v[x].tam+=(v[v[x].next[it.fi]].tam);
    }
    //cout<<x<<" "<<v[x].tam<<" "<<v[x].c<<"\n";
}

void solve(int x){
    vector<pic>gamb;
    int filho;
    for(auto it:v[x].next){
        filho=v[x].next[it.fi];
        gamb.pb({v[filho].tam, v[filho].c});
    }
    if(gamb.size()>1)sort(all(gamb));
    for(auto it:gamb){
        resp.pb(it.se);
        if(v[v[x].next[it.se]].id==1)resp.pb('P');
        solve(v[x].next[it.se]);
        resp.pb('-');
    }
}


int32_t main(){ faster
    int n;
    cin>>n;
    s.resize(n);
    for(int i=0; i<n; i++){
        cin>>s[i];
    }
    int x;
    inicio=new_node();
    sort(all(s));
    for(auto elem:s){
        x=inicio;
        for(auto it:elem){
            if(v[x].next.count(it)==0){
                v[x].next[it]=new_node();
            }
            x=v[x].next[it];
            v[x].c=it;
        }
        v[x].id=1;
    }
    dfs(inicio);
    solve(inicio);
    char aux=resp.back();
    while(aux=='-'){
        resp.pop_back();
        aux=resp.back();
    }
    cout<<resp.size()<<"\n";
    for(auto it:resp)cout<<it<<"\n";

}

/*
6
cavaloo
ba
ban
bana
banan 
banana
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...