제출 #1214043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1214043		leandroioilele	Type Printer (IOI08_printer)	C++20	100 / 100	215 ms	99324 KiB

printer

#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>
#define INF 9999999999
#define pis pair<int,string>
#define piic pair<int,pair<int,char>>

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

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

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

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

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

int32_t main(){
    int n;
    cin>>n;
    s.resize(n);
    string maior;
    for(int i=0; i<n; i++){
        cin>>s[i].se;
        if(s[i].se.size()>maior.size()){
            maior=s[i].se;
        }
    }
    int igual;
    for(int i=0; i<n; i++){
        igual=0;
        for(int j=0; j<min(maior.size(),s[i].se.size()); j++){
            if(maior[j]==s[i].se[j]){
                igual++;
            }
            else break;
        }
        s[i].fi=igual;
    }
    sort(all(s));
    inicio=new_node();
    int x;
    for(int i=0; i<n; i++){
        x=inicio;
        for(auto it:s[i].se){
            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";
}

• 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